@@ -0,0 +1,2669 @@
+package breadth_first_search;%0A%0Aimport java.util.*;%0A%0Apublic class Q1048LongestStringChain %7B%0A%0A    //Difficulty: medium%0A    //TAG: BFS%0A    //TAG: DFS%0A%0A    /**%0A     * 1048. Longest String Chain%0A     * Given a list of words, each word consists of English lowercase letters.%0A     *%0A     * Let's say word1 is a predecessor of word2 if and only if we can add exactly one letter anywhere in word1 to make it equal to word2.  For example, %22abc%22 is a predecessor of %22abac%22.%0A     *%0A     * A word chain is a sequence of words %5Bword_1, word_2, ..., word_k%5D with k %3E= 1, where word_1 is a predecessor of word_2, word_2 is a predecessor of word_3, and so on.%0A     *%0A     * Return the longest possible length of a word chain with words chosen from the given list of words.%0A     *%0A     *%0A     *%0A     * Example 1:%0A     *%0A     * Input: %5B%22a%22,%22b%22,%22ba%22,%22bca%22,%22bda%22,%22bdca%22%5D%0A     * Output: 4%0A     * Explanation: one of the longest word chain is %22a%22,%22ba%22,%22bda%22,%22bdca%22.%0A     *%0A     *%0A     * Note:%0A     *%0A     * 1 %3C= words.length %3C= 1000%0A     * 1 %3C= words%5Bi%5D.length %3C= 16%0A     * words%5Bi%5D only consists of English lowercase letters.%0A     */%0A%0A    /*%0A    Solution:%0A%0A    BFS, push all word in words into queue to bfs, try find max steps%0A%0A    Time: O(n!)%0A    Space: O(n)%0A     */%0A%0A    public int longestStrChain(String%5B%5D words) %7B%0A        Map%3CInteger, List%3CString%3E%3E map = new HashMap%3C%3E();%0A        Queue%3CString%3E queue = new LinkedList%3C%3E();%0A        for (String word: words) %7B%0A            int len = word.length();%0A            map.putIfAbsent(len, new ArrayList%3C%3E());%0A            map.get(len).add(word);%0A            queue.offer(word);%0A        %7D%0A        int step = 0;%0A        while (!queue.isEmpty()) %7B%0A            int size = queue.size();%0A            while (size-- %3E 0) %7B%0A                String poll = queue.poll();%0A                int len = poll.length();%0A                if (map.containsKey(len + 1)) %7B%0A                    for (String next: map.get(len + 1)) %7B%0A                        if (addOneLetter(poll, next)) queue.offer(next);%0A                    %7D%0A                %7D%0A            %7D%0A            step++;%0A        %7D%0A        return step;%0A    %7D%0A%0A    private boolean addOneLetter(String s1, String s2) %7B%0A        int count = 0;%0A        for (int i = 0, j = 0; i %3C s1.length() && j %3C s2.length(); i++, j++) %7B%0A            if (s1.charAt(i) != s2.charAt(j)) %7B%0A                if (count %3E 0) return false;%0A                count++;%0A                i--;%0A            %7D%0A        %7D%0A        return true;%0A    %7D%0A%0A    /*%0A    Solution:%0A%0A    DFS%0A    memorized, use hashMap filter max steps in words, when do dfs and find the word in map, return map.get(word)%0A    instead of keep dfs%0A%0A    Time: O(n)%0A    Space: O(n)%0A     */%0A%0A%7D%0A

1048. Longest String Chain