Update Longest String Chain.java

varunu28 · web-flow · commit 162a26bf7f65 · 2023-09-23T08:43:44.000-07:00
diff --git a/Medium/Longest String Chain.java b/Medium/Longest String Chain.java
@@ -1,29 +1,31 @@
 class Solution {
-  public int longestStrChain(String[] words) {
-    Map<String, Integer> dp = new HashMap<>();
-    Set<String> wordSet = Arrays.stream(words).collect(Collectors.toSet());
-    int maxLength = 0;
-    for (String word : words) {
-      maxLength = Math.max(maxLength, dfs(wordSet, dp, word));
+    public int longestStrChain(String[] words) {
+        Set<String> wordSet = Arrays.stream(words)
+        .collect(Collectors.toSet());
+        Map<String, Integer> memo = new HashMap<>();
+        int result = 0;
+        for (String word : words) {
+            result = Math.max(result, dfs(wordSet, memo, word));
+        }
+        return result;
     }
-    return maxLength;
-  }
-  
-  private int dfs(Set<String> wordSet, Map<String, Integer> dp, String currWord) {
-    if (dp.containsKey(currWord)) {
-      return dp.get(currWord);
+
+    private int dfs(Set<String> wordSet, Map<String, Integer> memo, String word) {
+        if (memo.containsKey(word)) {
+            return memo.get(word);
+        }
+        int maxLength = 1;
+        StringBuilder sb = new StringBuilder(word);
+        for (int i = 0; i < word.length(); i++) {
+            sb.deleteCharAt(i);
+            String newWord = sb.toString();
+            if (wordSet.contains(newWord)) {
+                int currLength = 1 + dfs(wordSet, memo, newWord);
+                maxLength = Math.max(maxLength, currLength);
+            }
+            sb.insert(i, word.charAt(i));
+        }
+        memo.put(word, maxLength);
+        return maxLength;
     }
-    int maxLength = 1;
-    StringBuilder sb = new StringBuilder(currWord);
-    for (int i = 0; i < currWord.length(); i++) {
-      sb.deleteCharAt(i);
-      String newWord = sb.toString();
-      if (wordSet.contains(newWord)) {
-        maxLength = Math.max(maxLength, 1 + dfs(wordSet, dp, newWord));
-      }
-      sb.insert(i, currWord.charAt(i));
-    }
-    dp.put(currWord, maxLength);
-    return dp.get(currWord);
-  }
 }
