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];
 }
}

• Maarten Bodewes: Code doesn't compile for Arrays.asList(toKey)...

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?

• Martin Frank: Thank you that you had also an eye on my answer! +1

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.

enter image description here

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!

• Martin Frank: k think it's called primitive obsession when you prefer primitive datatype Map<String, Integer> over a proper data type.
• Maarten Bodewes: That should be isSuccessor() the way you wrote it. The predecessor is the smaller of the words, and you compare to #word + 1.
• Maarten Bodewes: Or make that Predecessor.isPredecessorOf(String successor) I guess.
• Maarten Bodewes: This design is a ton better, but it really requires its own code review, to be honest.
• Maarten Bodewes: Something that really got me, even though it is very minimal, is breakReached = true; -> after the loop, if no break is reached, then the last character only differs, right? So success & stop! (but I upvoted for the design, because the errors don't invalidate it).