[leetcode] 1048. Longest String Chain

문제 : https://leetcode.com/problems/longest-string-chain/

---

먼저 words 배열을 문자열 길이 오름차순으로 정렬한다.

이제 반드시 [words[i], words[j]] (i < j) 식으로 string chain이 만들어진다.

longest length를 저장하는 map을 하나 만든다.

map<string, int> dp;

위 map에는 key : words[i], value : longest length of a word chain 이 들어간다.

이제 words를 앞에서부터 탐색한다.

탐색 중인 words 문자열을 word2라고 했을 때 word2에서 문자를 하나씩 빼면서 string chain을 만드는 word1인지 확인한다.

만약 string chain을 만들 수 있는 word1이라면 dp map에 값이 있을 것이다.

string chain을 만들 수 있는 word1이라면 dp[word1] + 1이 word2이 가질 수 있는 word chain length이다.

dp[word1] + 1 값 중 최대값이 dp[word2] 값이 된다.

words 배열을 모두 탐색하면서 dp map을 세팅했다면 value들 중 최대값이 정답이 된다.

 

시간복잡도는 N을 words.length, M을 words[i].length라 한다면 반복문을 도는데 O(NM)이 소요되고 map에서 length를 가져오는데  O(logN)이 소요되므로 총 시간복잡도는 O(NMlogN)이다.

 

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/1048.%20Longest%20String%20Chain.cpp