[leetcode][140] Word Break II

문제 : https://leetcode.com/problems/word-break-ii/

---

DFS를 돌리면 TLE가 발생해서 memoization을 추가했다.

dp[lastInd] = s[0 ~ lastInd] 로 만들 수 있는 정답 가능 문자열의 리스트이다.

즉 우리가 구할 건 dp[ |str| - 1 ].

 

문자열의 뒤에서부터 탐색을 하므로 wordDict의 문자열들의 마지막 문자를 key로 하는 dictionary를 하나 만들었다.

ex) wordDict = ["ab", "b", "ac"]  ->  dict ={ {'b', ["ab", "b"]}, {'c', ["c"]}}

 

dict에서 lastInd를 key로 하는 단어들을 가져온 뒤, 문자열의 서브 문자열이 가능한지 체크한다.

ex) banana a가 lastInd인 경우 dict에서 a를 키 값으로 하는 문자열들을 가져온다. 가져온 문자열들이 ["na", "ba"] 라면 "na"는 서브문자열이 가능(banana)하고 ba는 불가능(banana b가 n과 다르다)하다. 

 

가능한 경우, 해당 문자의 길이를 lastInd에서 뺀 뒤 dfs를 다시 돌린다. 함수에서 반환되는 문자열들 뒤에 문자를 붙인 뒤 반환한다.

ex) na가 가능하므로 banana에서 na를 제외한 lastInd를 구한 뒤 거기서 dfs를 다시돌린다. -> banana 인덱스가 3인 a를 기준으로 dfs를 돌린 결과 리스트가 ["ba na", "b ana"]인 경우 문자열들 뒤에 na를 붙인 후 현재 탐색 중인 dfs 결과 리스트에 추가한다. ["ba na na", "b ana na"]

 

dfs 결과 리스트를 반환하기 전에 dp[lastInd]에 결과 리스트를 저장한다.

dfs 함수 초반에 dp[lastInd]를 검사하고 이미 세팅이 되어있다면 이를 반환한다.(memoization)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/140.%20Word%20Break%20II.py

---

DICTIONARY.setdefault(KEY, DEFAULT_VALUE) :  DICTIONARY에서 KEY에 해당하는 value를 반환하고 없는 경우 DEFAULT_VALUE를 value로 저장한 후 반환한다.

DICTIONARY.get(KEY, DEFAULT_VALUE) : DICTIONARY에서 KEY에 해당하는 value를 반환하고 없는 경우 DEFAULT_VALUE를 반환한다.

str[S:E] : str 문자열의 인덱스가 [S, E)에 해당하는 부분문자열을 반환한다.