摘要：同時(shí)使用方法將數(shù)組轉(zhuǎn)化為并利用的直接比較兩個(gè)字符串是否相等。通過(guò)這種方法效率值提高了不少。
題目要求
Given an array of strings, group anagrams together.
For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
Return:
[
["ate", "eat","tea"],
["nat","tan"],
["bat"]
]
Note: All inputs will be in lower-case.
將含有相同的字母但是排序可能不同的單詞分類至不同的數(shù)組
思路一：不使用map（超時(shí)了）
這里利用了String的API方法toCharArray來(lái)對(duì)兩個(gè)單詞是否是相同字母組成的進(jìn)行比較。但是效率較低。這里有重復(fù)的無(wú)效操作，例如獲得當(dāng)前數(shù)組的第一個(gè)值并重新計(jì)算其對(duì)應(yīng)的有序char數(shù)組。而且比較兩個(gè)char數(shù)組的方法造成了三圈循環(huán)，帶來(lái)的O(n3)的時(shí)間復(fù)雜度
public List> groupAnagrams(String[] strs) {
List> result = new LinkedList>();
L1:for(int i = 0 ; i < strs.length ; i++){
String temp = strs[i];
int tempLength = temp.length();
L2:for(int j = 0 ; j currentList = result.get(j);
String currentString = currentList.get(0);
int currentStringLength = currentString.length();
if(currentStringLength>tempLength){
List newResult = new ArrayList();
newResult.add(temp);
result.add(j, newResult);
continue L1;
}else if (currentStringLength newResult = new ArrayList();
newResult.add(temp);
result.add(newResult);
}
return result;
}
public boolean isPermutation(String s1, String s2){
if(s1.length() != s2.length()){
return false;
}
char[] s1array = s1.toCharArray();
Arrays.sort(s1array);
char[] s2array = s2.toCharArray();
Arrays.sort(s2array);
for(int i = 0 ; i
思路二：利用String.valueof
其實(shí)在這里利用Map會(huì)減少重復(fù)的生成char數(shù)組的過(guò)程。同時(shí)使用String.valueof()方法將char數(shù)組轉(zhuǎn)化為String并利用String的API直接比較兩個(gè)字符串是否相等。通過(guò)這種方法效率值提高了不少。
public List> groupAnagrams2(String[] strs){
Map> map = new HashMap>();
for(String temp : strs){
char[] current = temp.toCharArray();
Arrays.sort(current);
String sortedTemp = String.valueOf(current);
if(!map.containsKey(sortedTemp)){
List tempResult = new ArrayList();
tempResult.add(temp);
map.put(sortedTemp, tempResult);
}else{
map.get(sortedTemp).add(temp);
}
}
return new ArrayList>(map.values());
}
想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.specialneedsforspecialkids.com/yun/70056.html
