1048. Longest String Chain
https://leetcode.com/problems/longest-string-chain/
문제
풀이(DFS)
내가 처음 풀었을 때 로직은 words를 길이에 맞게 다시 저장하는 것이다. 즉
Example 1에서 words = ["a","b","ba","bca","bda","bdca"]를 딕셔너리 wd = {}에 길이에 맞게 저장한다.
wd[(1)] = ['a', 'b']
wd[(2)] = ['ba']
wd[(3)] = ['bca', 'bda']
wd[(4)] = ['bdca'] 로 저장된다.
이제 words를 길이 역순으로 재정렬한다.
words = ['bdca', 'bda', 'bca', 'ba', 'b', 'a']가 될 것이다.
재정렬된 words에서 순서대로 체인을 찾는다. 즉
1. 'bdca'에서 길이가 3인 문자가 나올 경우의 수는 'dca', 'bca', 'bda', 'bdc'가 될 것이다.
2. 이제 구한 경우의 수중 wd[(3)]에 속한 것을 찾는다. 즉 'bca', 'bda가 될 것이다.
3. 'bca'에서 길이가 2인 문자가 나올 경우의 수를 찾는다. 'ca', 'ba', 'bc'가 될 것이고
4. 이제 구한 경우의 수중 wd[(2)]에 속한 것을 찾는다. 'ba'만 될 것이다.
5. 'ba'에서 길이가 1인 문자가 나올 경우의 수를 찾는다. 'b', 'a'가 될 것이고
6. 이제 구한 경우의 수중 wd[(1)]에 속한 것을 찾는다. 'b', 'a'일 것이다.
즉 (bdca, bca, ba, a) or (bdca, bca, ba, b) or (bdca, bda, ba, a) or (bdca, bda, ba, b)가 되고 최대값은 4가 된다.
DFS로 구현하면서 종료조건이 중요한데 small(words중 가장 작은 문자열 길이)가 될 때 리턴해주어야 한다.
또한 딕셔너리 wd에서 l-1키 값이 없을 수도 있다. 왜냐하면 words안에 있는 문자열 길이에 맞게 키값이 설정되어 있기 때문에 l-1 키값이 존재하지 않을 수 있다. 그러므로 예외조건를 추가하였다.결과(DFS)
