先看一眼题:
思路:遍历strs里的所有字符串,如果这个字符串已经被存到resList中,则跳过接下来的判断,继续看下一个字符串;如果resList中不存在有任何一个list包含该字符串,则用该字符串创建一个list,并加入到resList中去。
需要写一个辅助函数,用于判断两个字符串是否拥有的字母相同,只是位置不同,即判断两个词是不是异位词。
代码:
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> resList = new ArrayList<>();
for (String str : strs) {
boolean valid = false;//true代表已经放到resList中了,false代表我要开辟一个新的list,包含此str,放入到resList中
for (List<String> list : resList) {
for (String s : list) {
if (equales(s, str)) {
list.add(str);
valid = true;
break;
}
}
if (valid)
break;
}
if (!valid) {
List<String> newList = new ArrayList<>();
newList.add(str);
resList.add(newList);
}
}
return resList;
}
public boolean equales(String a, String b) {
//判断两个字符串是否是异位词
if (a.length() != b.length())
return false;
for (int i = 0; i < b.length(); i++) {
char c = b.charAt(i);
//把一个char转换为String需要使用Character
String substr = Character.toString(c);
if (!a.contains(substr)) {
return false;
}
//如果a里包含该字符,则将a去掉该字符
int j = a.indexOf(c);
a=a.substring(0,j)+a.substring(j+1,a.length());
}
return true;
}
效率:经典只打败5%的人的小垃圾运行效率。我还是太菜了。