ac solution code

• Solution1 - DP evolves from Solution2 - memorized DFS.

``````/*  Solution1. DP. time = O(n^2); space = O(n) - DP array

KEY:
1. Break string into words in dictionary
2. Backtracking: Fill i position with each of specified items, keep deeper, then backtrack

dp[i] is set to true if a valid word (word sequence) ends there
The optimization is to look from current position i back and only substring and do dictionary look up in case
the preceding position j with dp[j] == true is found.
*/
func wordBreak1(_ s: String, _ wordDict: [String]) -> Bool {
let n = s.characters.count
let dict = Set<String>(wordDict)                //O(n)
var f = [Bool](repeating: false, count: n + 1)  // 1. dp[i]: whether String(0..<i) can be broken into words in dictionary
f[0] = true

for i in 1 ..< n + 1 {                          // 2-1. Check String(j...i): i in i...n
for j in 0 ..< i {                          // 2-2. j in 0..<i
if f[j] && dict.contains(s.subString(j, i)) {
f[i] = true
break
}
}
}
return f[n]
}

/** Solution2. Memorized DFS. time = O(n^2); space = O(n)
The basic idea is:
1. Use memorized DFS map[s: breakable] to save prev result of s to avoid duplicates
*/
private var map = [String: Bool]() // [s: breakable]

func wordBreak(_ s: String, _ wordDict: [String]) -> Bool {
guard s.characters.count > 0 else { return wordDict.count == 0 }
var wordDict = Set<String>(wordDict)
return DFS(s, &wordDict)
}

private func DFS(_ s: String, _ wordDict: inout Set<String>) -> Bool {
if map[s] != nil { return map[s]! }                 // 1-1. Check memorized results
if s.characters.count == 0 {                        // 1-2. Exit case/append one path
return true
}

var result = false
for word in wordDict {                              // 2. For range
if s.hasPrefix(word) {                          // 2-1. Condition: prefix - matchs word in wordList. <- O(mn)
if DFS(s.removedPrefix(word), &wordDict) {  // 2-2. DFS
result = true
break
}
}
}

map[s] = result
return result
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.