dictionary1 [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가 l.. 2019. 12. 19. 이전 1 다음