1048. Longest String Chain / TypeScript

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.

 

Example 1:

Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: One of the longest word chains is ["a","ba","bda","bdca"].

Example 2:

Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
Output: 5
Explanation: All the words can be put in a word chain ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].

Example 3:

Input: words = ["abcd","dbqca"]
Output: 1
Explanation: The trivial word chain ["abcd"] is one of the longest word chains.
["abcd","dbqca"] is not a valid word chain because the ordering of the letters is changed.

 

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

 

풀이

function longestStrChain(words: string[]): number {
    words.sort((a, b) => a.length - b.length);

    const dp: { [key: string]: number } = {};

    let maxChain = 0;

    for (const word of words) {
        dp[word] = 1;
        for (let i = 0; i < word.length; i++) {
        const prev = word.slice(0, i) + word.slice(i + 1);
        if (prev in dp) {
            dp[word] = Math.max(dp[word], dp[prev] + 1);
        }
        }
        maxChain = Math.max(maxChain, dp[word]);
    }

    return maxChain;
};

 

주어진 문자열 배열 words에서 가장 긴 문자열 체인의 길이를 구하는 함수

알고리즘 풀이:

1. 문자열 배열 정렬: 주어진 문자열 배열 words를 각 문자열의 길이에 따라 오름차순으로 정렬.
2. 동적 계획법 (DP) 배열 생성: dp라는 객체를 사용하여 각 문자열에 대해 그 문자열이 만들 수 있는 최대 체인의 길이를 저장.
3. 각 단어에 대해 이전 문자열 찾기: 각 단어에 대해, 그 단어의 한 글자를 제거하여 만들 수 있는 "이전 문자열"을 찾음. 만약 그 이전 문자열이 이미 dp에 존재하면, 현재 문자열의 체인 길이를 갱신. 즉, dp[현재 단어]와 dp[이전 단어] + 1 중 더 큰 값을 취함.
4. 결과 반환: 모든 문자열을 처리한 후 가장 긴 체인의 길이를 반환

 

slice() 메서드 설명:

• slice() 메서드는 문자열의 특정 부분을 추출하고, 추출한 부분을 새로운 문자열로 반환
• 인자는 시작 인덱스와 끝 인덱스 두 개가 있는데, 끝 인덱스는 선택 사항.
  • slice(start) → start 인덱스부터 문자열 끝까지를 반환.
  • slice(start, end) → start 인덱스부터 end 인덱스 앞까지를 반환.

word.slice(1) 의미:

• 이 경우, slice(1)은 인덱스 1부터 끝까지의 문자열을 잘라내서 반환.
• 예를 들어:
  • "hello".slice(1) → "ello" (첫 글자인 "h"를 제외한 나머지 부분 문자열)
  • "apple".slice(1) → "pple" (첫 글자인 "a"를 제외한 나머지 부분 문자열)

즉, word.slice(1)은 첫 번째 문자를 제거한 문자열을 반환하는 것

 

 

   for (const word of words) {
        dp[word] = 1;
        for (let i = 0; i < word.length; i++) {
        const prev = word.slice(0, i) + word.slice(i + 1);
        if (prev in dp) {
            dp[word] = Math.max(dp[word], dp[prev] + 1);
        }
        }
        maxChain = Math.max(maxChain, dp[word]);
    }

 

예시로 설명:

1. word = "ba"일 때

• "ba"는 길이가 2인 문자열. 이 문자열의 한 글자를 제거

for (let i = 0; i < word.length; i++) {

• 첫 번째 반복 (i = 0):

const prev = word.slice(0, 0) + word.slice(1);  // word = "ba", i = 0

• 여기서 word.slice(0, 0)는 빈 문자열이 되고, word.slice(1)은 "a"가 됨.
• 즉, "ba"에서 첫 번째 글자인 "b"를 제거한 결과는 "a"

const prev = "a";  // "ba"에서 첫 번째 글자 제거

 

• 다음으로 dp에서 "a"가 있는지 확인

if (prev in dp) {
    dp["ba"] = Math.max(dp["ba"], dp["a"] + 1);  // dp["a"] + 1을 통해 체인 길이 갱신
}

• dp["a"]는 1. 따라서 dp["ba"]는 dp["a"] + 1로 갱신

dp["ba"] = 2;  // "ba"는 "a"에 이어서 체인을 이루므로, 체인 길이 2

 

 

• 두 번째 반복 (i = 1)

const prev = word.slice(0, 1) + word.slice(2);  // word = "ba", i = 1

• 여기서 word.slice(0, 1)은 "b"이고, word.slice(2)는 빈 문자열. 즉, "ba"에서 두 번째 글자인 "a"를 제거한 결과는 "b"가 됨

const prev = "b";  // "ba"에서 두 번째 글자 제거

• dp에서 "b"가 있는지 확인

if (prev in dp) {
    dp["ba"] = Math.max(dp["ba"], dp["b"] + 1);
}

 

 

• 여기서 dp["b"]는 1이므로, dp["ba"] = Math.max(2, 1 + 1)이 됨.
• 이미 dp["ba"]가 2로 설정되어 있으므로 변화는 없음.
• 결과적으로 dp["ba"] = 2가 유지

 

 

2. word = "bdca"일 때.

• "bdca"에서 각 글자를 하나씩 제거하는 과정을 따라가면:
  • i = 0: "bdca"에서 첫 번째 글자 "b"를 제거하면 "dca"가 됨. "dca"는 dp에 없으므로 무시
  • const prev = "dca";
  • i = 1: "bdca"에서 두 번째 글자 "d"를 제거하면 "bca"가 됨. "bca"는 dp에 존재하고, dp["bca"] = 3.
  • 따라서 dp["bdca"]는 dp["bca"] + 1 = 4로 갱신됨.
  • dp["bdca"] = 4;
  • const prev = "bca";
  • i = 2: "bdca"에서 세 번째 글자 "c"를 제거하면 "bda"가 됨. "bda"도 dp에 존재하며, dp["bda"] = 3.
  • 따라서 다시 한 번 dp["bdca"] = 4로 유지
  • const prev = "bda";
  • i = 3: "bdca"에서 네 번째 글자 "a"를 제거하면 "bdc"가 됨.
  • "bdc"는 dp에 없으므로 무시됩니다.
  • const prev = "bdc";
• 결과적으로 dp["bdca"]는 4로 유지

 

 

---

 

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

1. 문자열 배열 정렬

우선 words 배열을 문자열 길이에 따라 오름차순으로 정렬합니다. 정렬 후 배열은 다음과 같습니다:

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

 

2. 동적 계획법(DP) 배열 초기화

dp라는 객체를 만들어 각 문자열이 가질 수 있는 최대 체인의 길이를 저장.

또한, maxChain이라는 변수를 만들어 최장 체인의 길이를 저장.

모든 단어는 자기 자신만을 체인으로 가질 수 있으므로, 처음에는 각각의 체인 길이를 1로 설정

 

dp = {
    "a": 1,
    "b": 1,
    "ba": 1,
    "bca": 1,
    "bda": 1,
    "bdca": 1
};

 

 

 

3. 각 단어에 대해 이전 문자열 찾기 및 체인 길이 갱신

단어 "a":

• 길이가 1인 가장 짧은 단어이므로 이전 단어를 만들 수 없음.
• 따라서 dp["a"] = 1로 유지.
• 현재 maxChain = 1.

단어 "b":

• 마찬가지로 "b"도 길이가 1인 단어이므로 이전 단어를 만들 수 없음
• dp["b"] = 1로 유지.
• 현재 maxChain = 1.

단어 "ba":

• 이제 길이가 2인 단어 "ba"에 대해 처리.
• "ba"에서 한 글자를 제거한 경우:
  • i = 0일 때, "a"를 제거하면 "a"가 남음. dp["a"]는 1이므로, dp["ba"] = dp["a"] + 1 = 2로 갱신.
  • i = 1일 때, "b"를 제거하면 "b"가 남음. dp["b"]도 1이므로, dp["ba"] = dp["b"] + 1 = 2로 갱신.
• 결과적으로 dp["ba"] = 2.
• 현재 maxChain = 2.

단어 "bca":

• 길이가 3인 단어 "bca"에 대해 처리.
• "bca"에서 한 글자를 제거한 경우:
  • i = 0일 때, "b"를 제거하면 "ca"가 남음. "ca"는 dp에 없으므로 무시
  • i = 1일 때, "c"를 제거하면 "ba"가 남음. dp["ba"] = 2이므로, dp["bca"] = dp["ba"] + 1 = 3으로 갱신
  • i = 2일 때, "a"를 제거하면 "bc"가 남음. "bc"는 dp에 없으므로 무시
• 결과적으로 dp["bca"] = 3
• 현재 maxChain = 3.

단어 "bda":

• "bda"에 대해 처리
• "bda"에서 한 글자를 제거한 경우:
  • i = 0일 때, "b"를 제거하면 "da"가 남음. "da"는 dp에 없으므로 무시
  • i = 1일 때, "d"를 제거하면 "ba"가 남음. dp["ba"] = 2이므로, dp["bda"] = dp["ba"] + 1 = 3으로 갱신
  • i = 2일 때, "a"를 제거하면 "bd"가 남음. "bd"는 dp에 없으므로 무시.
• 결과적으로 dp["bda"] = 3
• 현재 maxChain = 3.

단어 "bdca":

• 마지막으로 "bdca"에 대해 처리
• "bdca"에서 한 글자를 제거한 경우:
  • i = 0일 때, "b"를 제거하면 "dca"가 남음. "dca"는 dp에 없으므로 무시
  • i = 1일 때, "d"를 제거하면 "bca"가 남음. dp["bca"] = 3이므로, dp["bdca"] = dp["bca"] + 1 = 4로 갱신
  • i = 2일 때, "c"를 제거하면 "bda"가 남음. dp["bda"] = 3이므로, dp["bdca"] = dp["bda"] + 1 = 4로 갱신
  • i = 3일 때, "a"를 제거하면 "bdc"가 남음. "bdc"는 dp에 없으므로 무시
• 결과적으로 dp["bdca"] = 4
• 현재 maxChain = 4.

4. 최종 결과

최종적으로 가장 긴 체인의 길이는 4.

"a" → "ba" → "bda" → "bdca"가 가장 긴 체인