Найти анаграмму ввода на множестве строк ..?

Question

Учитывая набор строк (большой набор) и входную строку, вам нужно эффективно найти все анаграммы входной строки. Какую структуру данных вы будете использовать. И используя это, как вы найдете анаграммы?

Вот о чем я подумал:

1. Использование карт

   а) исключить все слова, содержащие больше / меньше букв, чем ввод.

   б) поместить введенные символы в карту

   в) Пройдите по карте для каждой строки и посмотрите, присутствуют ли все буквы с их количеством.

2. Использование попыток

   a) Поместите в цепочку все строки с правильным количеством символов.

   b) пройти каждую ветвь и углубиться, если буква содержится во входных данных.

   в) если лист достигнет слова, это анаграмма

Кто-нибудь может найти лучшее решение?

Есть ли какие-либо проблемы, которые вы обнаружите в вышеупомянутых подходах?

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

Вы можете создать хэш-карту, в которой ключ сортируется (слово), а значение представляет собой список всех слов, которые, отсортированные, дают соответствующий ключ:

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