1048.Longest-String-Chain

1048. Longest String Chain

题目地址

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 1:
Input: ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: one of the longest word chain is "a","ba","bda","bdca".

Note:
1 <= words.length <= 1000
1 <= words[i].length <= 16
words[i] only consists of English lowercase letters.

代码

Approach #1 Dynamic Programming

class Solution {
  public int longestStrChain(String[] words) {
        Map<String, Integer> dp = new HashMap<>();
    Arrays.sort(words, (a, b) -> a.length() - b.length());
    int ans = 0;
    for (String word: words) {
      int best = 0;
      for (int i = 0; i < word.length(); i++) {
        String prev = word.substring(0, i) + word.substring(i + 1);
        best = Math.max(best, dp.getOrDefault(prev, 0) + 1);
      }
      dp.put(word, best);
      ans = Math.max(ans, best);
    }

    return ans;
  }
}

Approach #2 DFS

class Solution {
  public int longestStrChain(String[] words) {
    int ans = 0;
    Set<String> set = new HashSet<>();
    Map<String, Integer> map = new HashMap();
    for (String word: words) {
      set.add(word);
    }
    for (String word: words) {
      ans = Math.max(ans, dfs(map, set, word));
    }
    return ans;
  }

  private int dfs(Map<String, Integer> map, Set<String> set, String word) {
    if (map.containsKey(word)) return map.get(word);

    int cnt = 0;
    for (int i = 0; i < word.length(); i++) {
      String next = word.substring(0, i) + word.substring(i + 1);
      if (set.contains(next)) {
        cnt = Math.max(cnt, dfs(map, set, next));
      }
    }

    map.put(word, 1 + cnt);
    return 1 + cnt;
  }
}