在一组字符串中查找输入字符串..？

Question

给定一组字符串（大集合）和一个输入字符串，您需要高效地查找输入字符串的所有字母。你会使用什么数据结构。使用它，你将如何找到字形？我想到的

事情是这些：

1. 使用地图

   一）消除了比输入更多/更少字母的所有单词。

   二）把输入的字符在地图

   C）遍历地图每个字符串，看看是否所有字母都存在与他们的计数。

2. 使用尝试次数

   一）把具有字符正确的号码为线索的所有字符串。

   b）如果输入中包含字母，则遍历每个分支并进一步深入。

   c）若叶达到这个词是字谜

任何人都可以找到一个更好的解决方案？

在上述方法中是否有任何问题？

Answer 1

从每个单词构建一个频率图并比较这些图。

伪代码：

class Word 

    string word 
    map<char, int> frequency 

    Word(string w) 
    word = w 
    for char in word 
     int count = frequency.get(char) 
     if count == null 
     count = 0 
     count++ 
     frequency.put(char, count) 

    boolean is_anagram_of(that) 
    return this.frequency == that.frequency 

Answer 2

你可以建立其中关键的排序的的HashMap（字），并将该值是，排序的所有单词的列表，给予相应的键：

private Map<String, List<String>> anagrams = new HashMap<String, List<String>>(); 

void buildIndex(){ 
    for(String word : words){ 
     String sortedWord = sortWord(word); 
     if(!anagrams.containsKey(sortedWord)){ 
      anagrams.put(sortedWord, new ArrayList<String>()); 
     } 
     anagrams.get(sortedWord).add(word); 
    } 
} 

然后，您只需在刚刚构建的散列映射中查找已排序的单词，即可得到所有字母表的列表。

Answer 3

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(); 
} 
}