---
tags: leetcode
---

# [1048. Longest String Chain](https://leetcode.com/problems/longest-string-chain/)
---
# My Solution
## The Key Idea for Solving This Coding Question
## C++ Code

struct wordData {
    string word;
    int lscLen;
    wordData(string &word, int lscLen) : word(word), lscLen(lscLen) {}
};

class Solution {
public:
    int longestStrChain(vector<string> &words) {
        unordered_map<int, vector<wordData>> lenToWord;
        int maxWordLen = 0;
        for (auto &word : words) {
            lenToWord[word.size()].push_back(wordData(word, 1));
            if (maxWordLen < word.size()) {
                maxWordLen = word.size();
            }
        }

        int lscLen = 1;
        for (int len = maxWordLen; len >= 1; --len) {
            auto iter1 = lenToWord.find(len - 1);
            auto iter2 = lenToWord.find(len);
            if (iter1 == lenToWord.end() || iter2 == lenToWord.end()) {
                continue;
            }

            vector<wordData> &wordList1 = iter1->second;
            vector<wordData> &wordList2 = iter2->second;
            for (int i = 0; i < wordList1.size(); ++i) {
                for (int j = 0; j < wordList2.size(); ++j) {
                    if (isPredecessor(wordList1[i].word, wordList2[j].word)) {
                        wordList1[i].lscLen = max(wordList1[i].lscLen, 
                                                  wordList2[j].lscLen + 1);
                        lscLen = max(lscLen, wordList1[i].lscLen);
                    }
                }
            }
        }
        return lscLen;
    }

private:
    // Assume word2.size() - word1.size() == 1 is true.
    bool isPredecessor(string &word1, string &word2) {
        int i = 0, j = 0;
        bool firstDiffFound = false;
        while (i < word1.size() && j < word2.size()) {
            if (word1[i] == word2[j]) {
                ++i;
                ++j;
            } else {
                if (firstDiffFound) {
                    return false;
                }
                firstDiffFound = true;
                ++j;
            }
        }

        return true;
    }
};

## Time Complexity
## Space Complexity
# Miscellane
<!--
# Test Cases

["a","b","ba","bca","bda","bdca"]

["xbc","pcxbcf","xb","cxbc","pcxbc"]

["abcd","dbqca"]

["abcd","abc","bcd","abd","ab","ad","b"]

["a", "aa", "cc", "b", "c", "dd", "aaa", "x", "kk", "uuu", "aaaa", "f", "xx", "aaaaa"]

* Wrong Answer:

["bdca","bda","ca","dca","a"]

* Wrong Answer:

["ksqvsyq","ks","kss","czvh","zczpzvdhx","zczpzvh","zczpzvhx","zcpzvh","zczvh","gr","grukmj","ksqvsq","gruj","kssq","ksqsq","grukkmj","grukj","zczpzfvdhx","gru"]

* Wrong Answer:

["a","ab","ac","bd","abc","abd","abdd"]

-->