LeetCode - 1048. Longest String Chain

1048. Longest String Chain - medium

문제

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.

제한사항

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

입출력 예

Input: ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: one of the longest word chain is "a","ba","bda","bdca".

풀이

• DP

bool comp(const string& a, const string& b){
    return a.size() < b.size();
}

class Solution {
public:
    int longestStrChain(vector<string>& words) {
        int len = words.size();
        vector<int> res(len, 1);
        
        // 길이가 작은 단어순으로 정렬
        sort(words.begin() , words.end(), comp);

        for(auto i = 1 ; i < len ; ++i){
            // 단어의 길이가 1 이면 패스
            if(words[i].size() == 1)
                continue;

            int max = 0;
            for(auto j = 0 ; j < i ; ++j){
                // 단어의 길이가 하나 차이가 나야 word chain이 가능
                if(words[j].size() != words[i].size() - 1)
                    continue;
                
                // 첫번째 단어부터 현재단어 전까지 
                // 단어 하나 차이가 나는지 검사
                int checkWordIndex = 0;
                for(auto k = 0 ; k < words[i].size() && checkWordIndex < words[j].size(); ++k){
                    if(words[i][k] == words[j][checkWordIndex]){
                        ++checkWordIndex;
                    }
                }
                
                /// word chain이 가능한 단어중
                // 가장 긴 word chain의 수를 찾음
                if(checkWordIndex == words[j].size()){
                    if(max < res[j])
                        max = res[j];
                }
            }
            
            // 가장 긴 word chain의 수를 저장
            res[i] += max;
        }
        
        return *max_element(res.begin(), res.end());
    }
};