ac solution code


  • 0

    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
        }
    

Log in to reply
 

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