s********x
发帖数: 914 | 1 Time Limit Exceeded了
但感觉已经cache了intermediate result了
是不是这题assume只是26个小写英文字母呢，如果是的话，用array就更快？
贴一下code
class AnagramString {
boolean visited;
String str;
private Map map = null;
AnagramString(String s) {
this.str = s;
}
boolean isAnagram(String s) {
if (this.map == null) {
this.map = new HashMap(this.str.length());
for (int i = 0; i < this.str.length(); i++) {
char c = this.str.charAt(i);
map.put(c, map.containsKey(c) ? map.get(c) + 1 : 1);
}
}
Map m = new HashMap(this.map
);
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
Integer n = m.get(c);
if (n == null || n == 0) {
return false;
}
m.put(c, n-1);
}
return true;
}
}
public class Solution {
public ArrayList anagrams(String[] strs) {
Map> map = new HashMap
ArrayList>();
ArrayList result = new ArrayList();
for (String str : strs) {
ArrayList l = map.get(str.length());
if (l == null) {
l = new ArrayList();
l.add(new AnagramString(str));
map.put(str.length(), l);
} else {
boolean anagramExists = false;
for (AnagramString s : l) {
if (s.isAnagram(str)) {
anagramExists = true;
result.add(str);
if (!s.visited) {
s.visited = true;
result.add(s.str);
}
break;
}
}
if (!anagramExists) {
l.add(new AnagramString(str));
}
}
}
return result;
}
} |
l*****a
发帖数: 14598 | 2 please use
Map> to store ansgrams then you will get it
you can use sorted characters string as the key for each word
【在 s********x 的大作中提到】
: Time Limit Exceeded了
: 但感觉已经cache了intermediate result了
: 是不是这题assume只是26个小写英文字母呢，如果是的话，用array就更快？
: 贴一下code
: class AnagramString {
: boolean visited;
: String str;
: private Map map = null;
:
: AnagramString(String s) {
|
l*****a
发帖数: 14598 | 3 你这个isAnagram函数对吗？
str=“aabc” S=“abc”时候什么情况？
【在 s********x 的大作中提到】
: Time Limit Exceeded了
: 但感觉已经cache了intermediate result了
: 是不是这题assume只是26个小写英文字母呢，如果是的话，用array就更快？
: 贴一下code
: class AnagramString {
: boolean visited;
: String str;
: private Map map = null;
:
: AnagramString(String s) {
|
s********x
发帖数: 914 | 4 谢谢！
这个思路本来也有想到，感觉space开销很多。现在细想一下，确实不用inner loop的
linear search，应该会快很多。
已经过了OJ
class AnagramString {
boolean visited;
String str;
AnagramString(String s) {
this.str = s;
}
static String getKey(String s) {
char[] a = s.toCharArray();
Arrays.sort(a);
return new String(a);
}
}
public class Solution {
public ArrayList anagrams(String[] strs) {
Map> map = new HashMap
, HashMap>();
ArrayList result = new ArrayList();
for (String str : strs) {
HashMap m = map.get(str.length());
String key = AnagramString.getKey(str);
if (m == null) {
m = new HashMap();
m.put(key, new AnagramString(str));
map.put(str.length(), m);
} else {
AnagramString as = m.get(key);
if (as != null) {
result.add(str);
if (!as.visited) {
as.visited = true;
result.add(as.str);
}
} else {
m.put(key, new AnagramString(str));
}
}
}
return result;
}
}
【在 l*****a 的大作中提到】
: please use
: Map> to store ansgrams then you will get it
: you can use sorted characters string as the key for each word
|
s********x
发帖数: 914 | 5 这个应该只会在相同length的string的bucket里才会invoke这个function
【在 l*****a 的大作中提到】
: 你这个isAnagram函数对吗？
: str=“aabc” S=“abc”时候什么情况？
|
l*****a
发帖数: 14598 | 6 你这个辅助类有什么好处？
【在 s********x 的大作中提到】
: 谢谢！
: 这个思路本来也有想到，感觉space开销很多。现在细想一下，确实不用inner loop的
: linear search，应该会快很多。
: 已经过了OJ
: class AnagramString {
: boolean visited;
: String str;
:
: AnagramString(String s) {
: this.str = s;
|
s********x
发帖数: 914 | 7 主要用一个visited做mark，这样我的map不需要ArrayList，只要存第一个visited
string。应该内存会少用点。
而且因为result不在乎order，我不需要最后遍历这个map去collect所有的string
【在 l*****a 的大作中提到】
: 你这个辅助类有什么好处？
|
T******e
发帖数: 157 | 8 lz很下工夫啊，一个简单的anagram涉及到了这么多东西，态度值得学习。 |
