import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
/*
*Program for Find Anagrams from Given A string of Arrays.
*
*Program's Maximum Time Complexity is O(n) + O(klogk), here k is the length of word.
*
* By removal of Sorting, Program's Complexity is O(n)
* **/
public class FindAnagramsOptimized {
public static void main(String[] args) {
String[] words = { "gOd", "doG", "doll", "llod", "lold", "life",
"sandesh", "101", "011", "110" };
System.out.println(getAnaGram(words));
}
// Space Complexity O(n)
// Time Complexity O(nLogn)
static Set<String> getAnaGram(String[] allWords) {
// Internal Data Structure for Keeping the Values
class OriginalOccurence {
int occurence;
int index;
}
Map<String, OriginalOccurence> mapOfOccurence = new HashMap<>();
int count = 0;
// Loop Time Complexity is O(n)
// Space Complexity O(K+2K), here K is unique words after sorting on a
for (String word : allWords) {
String key = sortedWord(word);
if (key == null) {
continue;
}
if (!mapOfOccurence.containsKey(key)) {
OriginalOccurence original = new OriginalOccurence();
original.index = count;
original.occurence = 1;
mapOfOccurence.put(key, original);
} else {
OriginalOccurence tempVar = mapOfOccurence.get(key);
tempVar.occurence += 1;
mapOfOccurence.put(key, tempVar);
}
count++;
}
Set<String> finalAnagrams = new HashSet<>();
// Loop works in O(K), here K is unique words after sorting on
// characters
for (Map.Entry<String, OriginalOccurence> anaGramedWordList : mapOfOccurence.entrySet()) {
if (anaGramedWordList.getValue().occurence > 1) {
finalAnagrams.add(allWords[anaGramedWordList.getValue().index]);
}
}
return finalAnagrams;
}
// Array Sort works in O(nLogn)
// Customized Sorting for only chracter's works in O(n) time.
private static String sortedWord(String word) {
// int[] asciiArray = new int[word.length()];
int[] asciiArrayOf26 = new int[26];
// char[] lowerCaseCharacterArray = new char[word.length()];
// int characterSequence = 0;
// Ignore Case Logic written in lower level
for (char character : word.toCharArray()) {
if (character >= 97 && character <= 122) {
// asciiArray[characterSequence] = character;
if (asciiArrayOf26[character - 97] != 0) {
asciiArrayOf26[character - 97] += 1;
} else {
asciiArrayOf26[character - 97] = 1;
}
} else if (character >= 65 && character <= 90) {
// asciiArray[characterSequence] = character + 32;
if (asciiArrayOf26[character + 32 - 97] != 0) {
asciiArrayOf26[character + 32 - 97] += 1;
} else {
asciiArrayOf26[character + 32 - 97] = 1;
}
} else {
return null;
}
// lowerCaseCharacterArray[characterSequence] = (char)
// asciiArray[characterSequence];
// characterSequence++;
}
// Arrays.sort(lowerCaseCharacterArray);
StringBuilder sortedWord = new StringBuilder();
int asciiToIndex = 0;
// This Logic uses for reading the occurrences from array and copying
// back into the character array
for (int asciiValueOfCharacter : asciiArrayOf26) {
if (asciiValueOfCharacter != 0) {
if (asciiValueOfCharacter == 1) {
sortedWord.append((char) (asciiToIndex + 97));
} else {
for (int i = 0; i < asciiValueOfCharacter; i++) {
sortedWord.append((char) (asciiToIndex + 97));
}
}
}
asciiToIndex++;
}
// return new String(lowerCaseCharacterArray);
return sortedWord.toString();
}
}
比方說,你有一個字謎的候選人。您可以嘗試對輸入字符串和此字符串進行排序 - 排序後它們應該是相同的。你有沒有考慮過這種方法? – user998692
排序會給我額外的時間消耗。而我的上述方法是線性的,無需排序 –
假設平均字長在範圍[3,20]字符中......當對一個字進行排序時,您的數據比較有限。此外,一旦使用散列表預處理了整個字典,則每個後續對getAnagrams的調用都將是O(1),而在trie方法中不是這樣。 –