1048. Longest String Chain

/**

 * 1048. Longest String Chain

 * Given a list of words, each word consists of English lowercase letters.

 * 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, “abc” is a predecessor of “abac”.

 * A word chain is a sequence of words [word_1, word_2, …, word_k] with k >= 1, where word_1 is a predecessor of

 * word_2, word_2 is a predecessor of word_3, and so on.

 * Return the longest possible length of a word chain with words chosen from the given list of words.  */

See the solution to this problem on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/google/medium/LongestStringChain.java

This is an interesting problem in that it is rather long and needs to be broken down into smaller steps to solve in good time.

Observations:

1. You need to group strings by their length – map where key is length and value is collection of strings is a good choice
2. You need a way where you can match two strings to validate whether they are off by only one character.
3. You need a way to traverse the string chain graph to determine the maximum possible length – a recursive dfs based logic will work
   1. Don’t reprocess same word multiple times as it will waste cycles (store processed in a set and skip repeats)
   1. During traversal update max depth if its greater than that so far found.

Algorithm:

1. Store the words in a map keyed by the string length with values as collection of words
2. Create a method that can match whether two strings are exactly different by 1
3. Create a method that can traverses the collection of strings recursively with counting the depth as it moves from length of string to the next.
4. Call the method 3 repeatedly for each length of string with starting string to match as empty (handle empty as special case to signify beginning of traversal).

Here is the code:

(other helper methods can be found on the complete solution at github).

void processLength(Map<Integer, List<String>> mapList, int level, int lenSoFar, String priorStr) {
    //maxChainLen = Math.max(lenSoFar, maxChainLen);
    if (lenSoFar > maxChainLen) {
        maxChainLen = lenSoFar;
    }
    List<String> strsAtLevel = mapList.get(level);

    if (strsAtLevel != null) {
        for (String str : strsAtLevel) {
            //if a string has previously been processed, dont reprocess
            //reprocess is possible if visit a level fresh while the string had previously been processed
            if (processedStrings.contains(str)) {
                continue;
            }
            if (priorStr.isEmpty()) {
                processedStrings.add(str);
                processLength(mapList, str.length()+1, lenSoFar+1, str);
            } else if (match(priorStr, str)) {
                processedStrings.add(str);
                processLength(mapList, level+1, lenSoFar+1, str);
            }
        }
    }
}