LeetCode: Longest String Chain (Java)

Question

1. For the question, I had a pretty messy solution so I would like some advice on how to better use Java to make the code a bit cleaner.

2. Also, a semi-hack that I did that I'm not proud of is checking if words.length == 0 at the beginning and returning 0 if so, so that I can initialize int longestSeen = 1 (if there exists a word, the smallest chain must be at least 1).

   In reality, if we haven't processed the graph to find the longest chain, we should have int longestSeen = 0. My solution only adds to the adjacency list adjList if there exists a relation (e.g. 'ab' -> 'abc'), so for the case where there are no chains and every word is a lone island, I'm not checking for the longest chain length at all and am basically just straight up returning 1. This makes sense and would be more time efficient than initializing the adjList with all the words, but it feels hack-y to me.

3. I had int[] longestChain outside of the longestStrChain method and I'm not sure how to get around this.

Problem: https://leetcode.com/problems/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.

Example:

Input: ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: one of the longest word chain is "a","ba","bda","bdca".

Solution:

class Solution {
    int[] longestChain; // memoization for longest chain length for fromKey vertex
    
    public int longestStrChain(String[] words) {
        if (words.length == 0) {
            return 0;
        }
        Map<String, Integer> wordToIndex = new HashMap<>(words.length);
        Map<Integer, List<Integer>> adjList = new HashMap<>(words.length);
        longestChain = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            wordToIndex.put(words[i], i);
        }
        for (String word : wordToIndex.keySet()) {
            for (int i = 0; i < word.length(); i++) {
                String curr = word.substring(0, i) + word.substring(i+1, word.length()); // take one char out at a time for each word and see if it's part of words[]
                if (wordToIndex.keySet().contains(curr)) {
                    int fromKey = wordToIndex.get(curr);
                    int toKey = wordToIndex.get(word);
                    if (adjList.keySet().contains(fromKey)) {
                        List<Integer> vertices = adjList.get(fromKey);
                        vertices.add(toKey);
                        adjList.replace(fromKey, vertices);
                    } else {
                        adjList.put(fromKey, new ArrayList<Integer>(Arrays.asList(toKey)));
                    }
                }
            }
        }
        int longestSeen = 1; // longest string chain so far
        for (Integer fromVertexIdx : adjList.keySet()) {
            longestSeen = Math.max(longestSeen, getChainLength(fromVertexIdx, adjList));
        }
        return longestSeen;
    }
    
    private int getChainLength(int fromVertexIdx, Map<Integer, List<Integer>> adjList) {
        if (longestChain[fromVertexIdx] > 0) {
            return longestChain[fromVertexIdx];
        }
        longestChain[fromVertexIdx] = 1; // min string length is 1 (vertex contains no edges)
        if (adjList.keySet().contains(fromVertexIdx)) {
            for (Integer edge : adjList.get(fromVertexIdx)) {
                longestChain[fromVertexIdx] = Math.max(longestChain[fromVertexIdx], getChainLength(edge, adjList)+1);
            }
        }
        return longestChain[fromVertexIdx];
    }
}

Answer 1

As a speedup, I was expecting some sorting to be performed on size; I'm a bit surprised to only see maps in this regard. HashMaps behave well, but I wonder how much faster it would be if the size was taken care of before trying to find stuff by comparison (of hashes or values).

One problem I have with your solution in general is the naming of the variables. Yes, an index is an index and a vertice is a vertice. But an index of what?. It doesn't help if you then throw everything on one heap; one method with a single helper method. The method goes 4 deep and contains other branches as well.

class Solution {

Ah, yes, that's of course not a good distinguishing class name.

int[] longestChain; // memoization for longest chain length for fromKey vertex

That doesn't seem right to me, just forward it using a parameter, but don't use fields unless necessary (e.g. this makes the function not-thread safe, while accomplishing nothing). Furthermore, in Java you don't declare anything until you're prepared to initialize it.

if (words.length == 0) {
    return 0;
}

Using a special case for zero is nothing to be ashamed of. Zero is such a special number that the Romans didn't even have a representation of it. However, it does make sense to check if your algorithm doesn't run even if you have a zero (does it?).

Map<Integer, List<Integer>> adjList = new HashMap<>(words.length);

To a new developer it is entirely unclear what adjList means here.

for (int i = 0; i < words.length; i++) {
    wordToIndex.put(words[i], i);
}

This should be performed in a separate method, so that you get the least amount of loops (and don't use i to mean separate things).

 String curr = word.substring(0, i) + word.substring(i+1, word.length()); // take one char out at a time for each word and see if it's part of words[]

What about smallerWord or similar as name instead of curr?

Answer 2

Data Design

your major flaw is your poor data design. As described in the question you have

1. find out when one word is a predecessor of another
2. A word chain is a sequence of words, where one word is a predecessor of another

1. find out when one word is a predecessor of another

this describes an algorithm on how to find out if one word is a predecessor of another. you should provide at least one method that does only this and only this:

private final String word;

public boolean isPredecessor(String predecessor) {
    if (predecessor == null) {
        return false;
    }
    if (predecessor.length() != word.length() + 1) {
        return false;
    }
    if(predecessor.length() == 1){
        return true;
    }
    boolean breakReached = false;
    int breakIndex = 0;
    for (int index = 0; index < word.length(); index++) {
        if (word.charAt(index) != predecessor.charAt(index)) {
            breakReached = true;
            breakIndex = index;
            break;
        }
    }
    for (int index = breakIndex; index < word.length(); index++) {
        if (breakReached && word.charAt(index) != predecessor.charAt(index+1)) {
            return false;
        }
    }
    return true;
}

compare letter by letter and if you come to one breaking difference you continue with index+1 - if all other match, then we have a predecessor. You iterate only once over the whole word.

2. A word chain is a sequence of words, where one word is a predecessor of another

that leads to the following data structure where you can store a word and its predecessors. Such a data structure makes the code very clearly to read later.

public class Predecessor {

    private final String word;
    private final List<Predecessor> predecessors = new ArrayList<>();

    public Predecessor(String word){
        this.word = word;
    }

    public void addPredecessor(Predecessor predecessor){
        predecessors.add(predecessor);
    }


    public List<Predecessor> getPathToRoot(){
        List<Predecessor> path = new ArrayList<>();
        if(!predecessors.isEmpty()){
            path.add(this);
            path.addAll(predecessors.get(0).getPathToRoot());
        }
        return path;
    }

    public boolean isPredecessor(String predecessor) {...}

    @Override
    public String toString(){
        if (!predecessors.isEmpty()){
            return "['"+word + "'->'"+predecessors.get(0).word+"']";
        }
        return "['"+word + "']";
    }

}

applied output

the algorithm with these applied methods and data structure would be fairly clear:

public int longestStrChain(String[] words) {

    //create predecessor list 
    List<Predecessor> predecessors = new ArrayList<>();
    for(String word: words){
        Predecessor newOne = new Predecessor(word);
        predecessors.add(newOne);
        for(Predecessor predecessor: predecessors){
            if(predecessor.isPredecessor(word)){
                predecessor.addPredecessor(newOne);
                predecessors.add(newOne);
                break;
            }
        }
    }

    //find out the longest one
    List<Predecessor> candidate = null;
    int depth = 0;
    for(Predecessor predecessor: predecessors){
        List<Predecessor> path = predecessor.getPathToRoot();
        if (path.size() > depth){
            depth = path.size();
            candidate = path;
        }
    }

    System.out.println(candidate);
    return candidate.size();
}

notes

since the data structure provide information from a --> to b it's result is -1 to the original size

[a --> ba] , [ba --> bca] , [bca --> bdca]

notes

since we don't care which predecessor we choose (predecessors.get(0)) it's a bit unpredictable which word chain we get. - but we're guaranteed to find one longest!