Skip to main content
Code Review

Return to Question

Commonmark migration
Source Link

  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.

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.

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

  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.

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

  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.

Tweeted twitter.com/StackCodeReview/status/1231051307332534273
created an actual list out of the questions / split into sections
Source Link

  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).

(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.

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

(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.

  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.

  1. I had int[] longestChain outside of the longestStrChain method and I'm not sure how to get around this.
Source Link
togepi
  • 85
  • 1
  • 6

LeetCode: Longest String Chain (Java)

(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];
 }
}
lang-java

AltStyle によって変換されたページ (->オリジナル) /