[leetcode 139] Word Break

139. Word Break

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

해결 과정

s를 wordDict 리스트 아이템들의 조합으로 만들 수 있을 때 true를 반환하는 문제다.

• j ~ i 번째 string이 주어진 리스트 아이템들의 조합로 만들 수 있다면, j가 0번째 일 때 또는 j-1 번째까지 조건을 만족하는지를 검사하고 i 번째 까지도 조건이 만족함을 저장한다.
  • j: 출발 index, i: 도착 index
  • s 를 substring() 하며 모든 케이스를 검사

[sample]

• true
  • s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “an”, “cat”]
• false
  • s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]

코드

fun wordBreak(s: String, wordDict: List<String>): Boolean {
  var memo = BooleanArray(s.length) { false }
  for(i in 0..s.length-1) to@{
    for(j in 0..i) from@{
      val current = s.substring(j, i+1)
      for(word in wordDict) {
        if(current == word) {
          if(j==0 || memo[j-1]) {
            memo[i] = true
          }
        }
      }
    }
  }
  return memo[s.length-1]
}

배운 점

작은 문제가 반복되는 큰 문제일 때는 memoization 과 함께 DP 문제로 풀 수 있다.