问一下OJ的Anagrams那道题# JobHunting - 待字闺中
s*x
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 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;
}
}
但感觉已经cache了intermediate result了
是不是这题assume只是26个小写英文字母呢，如果是的话，用array就更快？
贴一下code
class AnagramString {
boolean visited;
String str;
private Map
AnagramString(String s) {
this.str = s;
}
boolean isAnagram(String s) {
if (this.map == null) {
this.map = new HashMap
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
);
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
Map
ArrayList
for (String str : strs) {
ArrayList
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;
}
}
