[leetcode][139] Word Break

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

---

문자열 s, 단어 리스트가 주어질 때 단어 리스트들로 문자열 s를 만들 수 있는지 구하는 문제.

단어는 사용하지 않아도 되고 여러번 사용해도 된다.

 

DP로 해결했다.

dp[i] = s[i..]를 단어 리스트로 만들 수 있는지 여부(true, false) 저장.

index를 기준으로 s[index]와 문자[0]가 같다면 s[index~] prefix가 문자와 같은지 비교하고 같다면 index+문자길이를 index로 다시 탐색한다. 

만약 탐색중 dp[index]가 이미 있다면 이를 반환한다. (이미 s[index..]를 탐색했다는 것을 의미)

 

시간복잡도는 O(|s| x |wordDict|). 문자가 같은지 비교해야 되기 때문에 실제로는 |wordDict[i]|가 추가로 소요된다.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/139.%20Word%20Break.cpp