[LeetCode] 139. Word Break

문제

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

Word Break - LeetCode

———————————————————————————

 

잠깐만

word를 체크할때마다, 재귀함수를 호출하지 말고, 체크를 해볼까요????

———————————————————————————

 

코드

class Solution {
    func wordBreak(_ s: String, _ wordDict: [String]) -> Bool {
        var checkWord: [Bool] = Array(repeating: false, count: s.count+1)
        checkWord[0] = true
    
        for endIndex in 1...s.count {
            for startIndex in (0...endIndex-1).reversed() {
                let word = String(Array(s)[startIndex...endIndex-1])
                if checkWord[startIndex], wordDict.contains(word) {
                    checkWord[endIndex] = true
                    break
                }
            }
        }
        return checkWord[checkWord.count-1]
    }
}

———————————————————————————

 

설명

해답은 체크 boolean에 있었습니다.

 

string인 s를 탐색하며, subString으로 쪼개고, wordDict에 존재할 경우, 단어의 마지막 알파벳 위치에 true로 체크합니다.

(이전 true의 위치 + 1)...(다음 true의 위치)까지 범위에 해당하는 단어가 wordDict에 존재한다는 의미입니다.

 

이번은 알아보기 쉽게 로그를 찍어봤습니다.

 

먼저 c를 wordDict에 검색하는데 wordDict에는 존재하지 않습니다.

그래서 endIndex를 1에서 2로 변경하여 단어를 탐색합니다.

 

이번엔 "a"와 "ca"를 wordDict에 검색하는데 wordDict에는 존재하지 않습니다.

그래서 endIndex를 3으로 변경하여 단어를 탐색합니다.

 

이번엔 "t"와 "at"를 wordDict에 검색하는데 wordDict에는 존재하지 않습니다.

"cat"를 검색하니, wordDict에 존재하네요. 그래서 "cat"이란 단어의 알파벳 "t"위치에 check(true)합니다.

endIndex를 4로 변경하여 단어를 탐색합니다.

 

이번엔 "s"와 "ts", "ats"를 wordDict에 검색하는데 wordDict에는 존재하지 않습니다.

"cats"를 검색하니, wordDict에 존재하네요. 그래서 "cats"이란 단어의 알파벳 "s"위치에 check(true)합니다.

T가 위치한 곳은, wordDict에 포함된 단어를 연속해서 이어붙여 완성할수 있다는 의미입니다.

endIndex를 5로 변경하여 단어를 탐색합니다.

 

이번엔 "a"부터 시작하여, "catsa"까지 wordDict에 존재하는지 찾아봤습니다.

존재하지 않았네요.

endIndex를 다음으로 변경합니다.

 

이번엔 "n"부터 시작하여, "catsan"까지 wordDict에 존재하는지 찾아봤습니다.

존재하지 않았네요.

endIndex를 다음으로 변경합니다.

 

"d"부터 "and"를 검색해보니, "ans"가 wordDict에 존재합니다.

따라서 "d"위치에 check를 해줍니다.

다음 endIndex로 이동합니다.

 

 

(중간 로그가 너무 많아 생략합니다.)

다음 단어에 대해 검색해봤는데, 존재하지 않아 알파벳 "g"의 check는 false로 끝났네요.

해당 입력에 대한 결과는 false입니다.

 

로그를 보니, 로직이 이해되죠?

 

로그를 구현한 코드를 추가하겠습니다.

//let s = "leetcode"
//let wordDict = ["leet","code"]

//let s = "leetcode"
//let wordDict = ["leet", "code"]

//let s = "a"
//let wordDict = ["a"]

//let s = "aaaaaaa"
//let wordDict = ["aaaa","aaa"]

let s = "catsandog"
let wordDict = ["cats","dog","sand","and","cat"]

//let s = "a"
//let wordDict = ["b"]

print(solution(s, wordDict))

func solution(_ s: String, _ wordDict: [String]) -> Bool {
    var checkWord: [Bool] = Array(repeating: false, count: s.count+1)
    checkWord[0] = true
    
    for endIndex in 1...s.count {
        print("--------------- move endIndex \(endIndex) ---------------")
        for startIndex in (0...endIndex-1).reversed() {
            print("--------------- move startIndex \(startIndex)")
            let word = String(Array(s)[startIndex...endIndex-1])
            logInputWord(s: s)
            
            logSearchWord(startIndex: startIndex, word: word)
            
            if checkWord[startIndex], wordDict.contains(word) {
                checkWord[endIndex] = true
                logCheckWord(checkWord: checkWord)
                logWordRange(range: "\(startIndex) ~ \(endIndex)")
                print("search success\n")
                break
            } else {
                logCheckWord(checkWord: checkWord)
                logWordRange(range: "\(startIndex) ~ \(endIndex)")
                print("")
            }
        }
    }
    return checkWord[checkWord.count-1]
}

func logInputWord(s: String) {
    print("input word  :  ", terminator: " ")
    s.forEach {
        print("\($0)", terminator: " ")
    }
    print("")
}

func logSearchWord(startIndex: Int, word: String) {
    print("search word :  ", terminator: " ")
    for index in 0..<startIndex {
        print(" ", terminator: " ")
    }
    
    word.forEach {
        print($0, terminator: " ")
    }
    print("")
}

func logCheckWord(checkWord: [Bool]) {
    print("check Array :", terminator: " ")
    checkWord.forEach {
        let result = $0 ? "T" : "f"
        print("\(result)", terminator: " ")
    }
    print("")
}

func logWordRange(range: String) {
    print("word range  : range")
}

———————————————————————————

 

회고

아쉽지만 저는 문제를 풀지 못했습니다 ㅠㅜㅠㅜㅠ

풀이 코드를 보니, 빡세네요.

시간이 흘러, 꼭 다시 풀어보겠습니다.