Longest String Chain

문자열 벡터를 받고 문자열끼리 체인을 이루는 집합 중 가장 큰 크기를 구하면 된다.

문자의 체인은 문자열의 순서를 바꾸지 않고,

문자열에 하나의 문자를 추가해서 문자열 벡터에 있는 문자가 될 때를 말한다.

class Solution {
public:
    int longestStrChain(vector<string>& words) {
        
        sort(words.begin(), words.end(), 
            [] (const auto &lhs, const auto &rhs)
            {
                return (lhs.size() < rhs.size());
            });
        
        unordered_map<string, int> wordTable{};
        
        int result{1};

        for (string &word : words)
        {
            int wordSize = word.size();
            for (int i = 0; i < wordSize; i++)
            {
                string tempWord{word};
                tempWord.erase(i, 1);
                int x = wordTable[tempWord];
                
                wordTable[word] = max(wordTable[word], x + 1);
                
                result = max(result, wordTable[word]);
            }
        }
        
        return result;
    }
};