[LeetCode] 1048. Longest String Chain

https://leetcode.com/problems/longest-string-chain/description/

LeetCode - The World's Leading Online Programming Learning Platform

문제 유형 : 다이나믹 프로그래밍 / 문자열 처리

문제 난이도 : Medium

 

 

You are given an array of words where each word consists of lowercase English letters.

wordA is a predecessor of wordB if and only if we can insert exactly one letter anywhere in wordA without changing the order of the other characters to make it equal to wordB.

• For example, "abc" is a predecessor of "abac", while "cba" is not a predecessor of "bcad".

A word chain is a sequence of words [word1, word2, ..., wordk] with k >= 1, where word1 is a predecessor of word2, word2 is a predecessor of word3, and so on. A single word is trivially a word chain with k == 1.

Return the length of the longest possible word chain with words chosen from the given list of words.

 

문자열 배열 words에는 영소문자로 구성된 단어들이 들어있다.

 

wordA의 어느 곳에 한 문자를 삽입하여  wordB 를 만들 수 있다면, wordA는 wordB의 전임자이다.

문자 체인은 앞의 단어가 뒤의 단어의 전임자로, 뒤의 단어가 앞의 단어의 전임자로 이어지는 것을 말한다.

조건을 만족하는 가장 긴 문자 체인의 길이를 반환시켜라.

 

문제 풀이

우선, words 배열을 문자가 가장 짧은순으로 정렬시킨다. 길이가 같으면 사전순으로 되게 하였다.

문자 체인을 담는 dp를 만든다. dp[i]는 i번째를 꼭 넣는 문자 체인이다.

 

배열을 순회하면서 다음 과정을 거친다:

1. 이전 체인들 중에서 연결 가능하면서 가장 긴 체인을 찾는다.

2. 그 체인에 연결한다.

3. 가장 긴 체인의 길이를 업데이트한다.

 

체인의 연결 가능 여부(전임자 확인)는 다음과 같이 한다:

1. 두 배열의 길이 차이가 1이 아니라면, 전임자 관계가 될 수 없다.

2. 두 문자열을 인덱스 0부터 비교해본다.

글자가 같으면 같이 인덱스를 더하고, 다르면 더 더 긴 문자열(후임자가 될 예정인)을 참조하는 인덱스만 1을 더한다.

3.순회가 정상적으로 끝냈는지 확인한다.

 

그 뒤, 가장 긴 길이를 반환해주면 된다.

 

코드

C++

class Solution {
public:
    bool isPredecessor(string A, string B)
    {
        int n = A.size();
        int m = B.size();

        if(m-n != 1) return false;

        int a = 0;
        int b = 0;

        while (a < n && b < m) {
        if (A[a] != B[b]) {
            b++;
        } else {
            a++;
            b++;
        }
    }

        return a == n;
    }

    int longestStrChain(vector<string>& words) {
        const int n = words.size();
        vector<vector<string>> dp(n);

        sort(words.begin(), words.end(), [](const string &a, const string &b) {
            if(a.size() == b.size()) {
                return a < b;
            }
            return a.size() < b.size();
        });

        dp[0].push_back(words[0]);

        int longestLength = -1;
        for(int i = 1; i < n; i++) {
            int idxToAppend = -1;
            int longestIdx = 0;
            for(int j = i-1; j >= 0; j--) {
                if(dp[j].size() >= longestIdx && isPredecessor(words[j], words[i])) {
                    idxToAppend = j;
                    longestIdx = dp[j].size();
                }
            }
            if(idxToAppend != -1){
                dp[i].assign(dp[idxToAppend].begin(), dp[idxToAppend].end());
            }
            dp[i].push_back(words[i]);

            longestLength = max(longestLength, static_cast<int>(dp[i].size()));
        }

        if(longestLength <= 0) {
            longestLength = 1;
        }
        return longestLength;
    }
};