1048. Longest String Chain

• String chain에서 WORD(k)는 WORD(k-1)에서 한 글자를 추가해서 만들어진다는 사실을 뒤집어서 생각하면 풀 수 있는 문제.
• 계속 글자를 추가하는 방식으로 풀어야 한다고 생각해서 못 풀었던 것 같다 (시간 제한에 걸렸다).

• 현재 단어 WORD(K)에서 임의의 위치에 있는 한 글자를 뺀 것 subWord = WORD(k-1) 중 chain의 길이가 가장 긴 것 chains[subWord] + 1 을 현재 단어의 chain 길이 chains[word] 로 한다.

class Solution {
public:
    int longestStrChain(vector<string>& words) {
        auto compare = [](string& a, string& b) {
            return a.length() < b.length();
        };
        sort(words.begin(), words.end(), compare);
        int result = 0;
        unordered_map<string, int> chains;
        for (auto& word : words) {
            int subResult = 0;
            for (int i = 0; i < word.length(); ++i) {
                auto subWord = word;
                subWord.erase(i, 1);
                subResult = max(subResult, chains[subWord] + 1);
            }
            chains[word] = subResult;
            result = max(result, subResult);
        }
        return result;
    }
};