[Leet Code] Longest String Chain

こんにちは!
今日、5月の3週目に3番目のアルゴリズムLongest String Chainプールを作成します.

質問する

サマリ
与えられたwordsでは、文字列間に関連するchain関係を見つけ、最も長いchainを返す.

初志

まず、wordsを長さ順に並べ、次に最短のStringから順に、次のStringの中にStringが現在含まれているかどうかをチェックし、最大のcountを返します."bdca".contains("bda")はfalseを導出したので,論理的誤りを感じた.

第二の考え方

じゃ、逆に探しましょう.wordsを長さ降順に並べ、Stringを逐字削除して配列に含まれるかどうかを判断します.
これは問題であり、chainから1つの語に至るため、dfs方式が適用される.
論理について詳しく説明しましょう.

コードの説明

int maxChain = 0;
Set<String> wordSet = new HashSet<>();
Map<String, Integer> wordChainMap = new HashMap<>();

maxChainは、最長チェーン長を格納する変数である.words配列の単語をwordSetに保存し、chainのwordChainMapまで保存できることを宣言します.

for (String word: words) {
    wordSet.add(word);
}

wordSetに単語を格納します.

for (String word: words) {
    maxChain = Math.max(maxChain, dfs(wordChainMap, wordSet, word));
}

単語chainを1つずつ解きます.ここではdfs関数が表示されます.dfs関数の値とmaxChainの値を比較し、より大きな値をmaxChainに格納します.dfs関数

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

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

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

この語が既にmapに存在する場合、その語のchain長さmap.get(word)が返される.
これにより、dfs論理の時間が大幅に減少します.検査済みのwordのchainを繰り返し検査する必要はないからです.mapに単語が存在しない場合、chainを初期化してcountの長さを取得する.
そして、wordの長さでforゲートの巡回を行い、wordから逐字除外してcompareWordを作成する.
すべてのwordがsetに格納されている場合、compareWordがchainに含まれる可能性があるため、countがチェックされる.
チェック時にcompareWordまでのチェーン長を計算する必要があるため、dfs関数を再呼び出す必要があります.
すべての可能な鎖長compareWordにおいてmaxの値が求められる場合、mapにはwordおよびcount + 1が格納される.
原因はcount + 1で、現在はwordまで計算する必要があるため、1を増やした.

完全なコード

class Solution {
    public int longestStrChain(String[] words) {
        int maxChain = 0;
        Set<String> wordSet = new HashSet<>();
        Map<String, Integer> wordChainMap = new HashMap<>();

        for (String word: words) {
            wordSet.add(word);
        }

        for (String word: words) {
            maxChain = Math.max(maxChain, dfs(wordChainMap, wordSet, word));
        }

        return maxChain;
    }

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

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

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

の最後の部分

昨日、今日はdfsアルゴリズムを使用して問題を解決しました.
昨日dfsの問題を解いたのか分からないが、今回は少し早く解決したようで、私はとても喜んでいます.
今回の位置付けを読んでいただき、フィードバックエラーを歓迎します:)