Find all possible sentences by anagrams-CodePudding

I have a list of words and a list of sentences.

First I want to find the anagrams from the list of words.

Next, I want to find the number of different sentences I can make by replacing any anagram word

This is what I tried:

I have created a map with the key as the sorted word and the value as the number of words that are anagrams for the selected key. Then pick a sentence from the given sentences list and pass it to the below method.

    static int getPossibleCount(String sentence, Map<String, List<String>> map) {
        int count = 0;
        String[] str = sentence.split(" ");
        for (String s : str) {
            char[] ar = s.toCharArray();
            Arrays.sort(ar);
            String key = new String(ar);
            int size = map.getOrDefault(key, new ArrayList<>()).size();
            if (size > 1) {
                count  = size;
            }
        }
        return count;
    }

This program works for this simple test case. I am not sure what is the correct logic to put inside getPossibleCount method. The approach I followed here does not count all possibilities if input range is increased.

Constraints:

The number of words ranges from 1 to 10^5
The length of each word ranges from 1 to 20
The number of sentences ranges from 1 to 1000
The number of words in each sentence ranges from 3 to 20.

CodePudding user response：

Each sentence will have at least 1 variation (which is the sentence itself). For each word in the sentence, the number of variations gets multiplied by the anagram count for the word.

More formally, for the sentence S = A B C, where A, B, C are words, getPossibleCount(S) = f(A) * f(B) * f(C), where f(X) = number of available anagrams for X.

    static int getPossibleCount(String sentence, Map<String, List<String>> map) {
        int count = 1;
        String[] str = sentence.split(" ");
        for (String s : str) {
            char[] ar = s.toCharArray();
            Arrays.sort(ar);
            String key = new String(ar);
            int size = map.getOrDefault(key, new ArrayList<>()).size();
            if (size > 1) {
                count *= size;
            }
        }
        return count;
    }