139. Word Break

Word Break

Word Break - LeetCode

- 문제 내용 : 주어진 문자열을 주어진 문자의 그룹으로 표현이 가능한가?

- 접근 방법

모든 경우의 수를 처리한다

s = "leetcode", wordDict = ["leet","leets", "code"]

가 주어졌다고 했을때

leet와 code로 구성되어있는지 확인 하는 방법이 있고,

leets와 ode로 구성되어있는 확인 하는 방법이 있다.

하지만 이 방법은 다소 문제가 있다.

만약에 아래와 같이 주어진 문제가 있다고 생각해 보자.

s = "aaaaaaaaaa", wordDict = ["a","aa", "aaa"]

a와 aaaaaaaaa로 이루어진 경우의 수

aa와 aaaaaaaa로 이루어진 경우의 수

aaa와 aaaaaaa로 이루어진 경우의 수가 생긴다.

여기서 다시 한번 

aaaaaaaaa는 

a와 aaaaaaaa로 이루어진 경우의 수

aa와 aaaaaaa로 이루어진 경우의 수

aaa와 aaaaaa로 이루어진 경우의 수가 생긴다.

즉 최대 N개의 wordDict가 있다고 하면 S의 길이가 길때 N^N의 횟수로 처리 범위가 엄청나게 늘어나게 된다.

위의 짧은 예봐 봐도 3가지 경우의 수에 다시 3가지 경우의 수 3 * 3이 생긴 것을 확인 할 수 있다.

이를 지속처리 해보면 n^n의 Time complexity가 나타나게 된다.

이것을 해결하는 방법은 Memorization을 사용하는 것이다.

상기 예를 조금 줄여 보도록 하겠다.

s = "aaaaaaa", wordDict = ["a","aa", "aaa"]

있다고 하면 나올 수 있는 경우의 수는 다음과 같다.

• a + aaaaaaa
  • a + aaaaaa
    • a + aaaaa
      •  .....
      • • a => true
    • aa + aaaa
    • aaa + aaa
  • aa + aaaaa
  • aaa + aaaa
• aa + aaaaaa
• aaa + aaaaa

상기와 같이 a가 true라는 사실을 알게 되고

a + aaaaa

가 true라는 사실을 저장해 놓는다면 

• aa + aaaaaa

와 같이 a가 6개인 경우는 true 임으로 더 이상 처리 할 필요 없이, true 처리 되면 된다.

이와 같은 Memorization을 바탕으로 O(N^2)까지 Time complexity가 내려가게 된다.

Memorization의 시간 복잡도는 아직도 어떻게 계산해야 할지 모르겠다. 그래서 다른 사람이 정리해 놓은 링크를 걸어 놓는다.

https://leetcode.com/problems/word-break/discuss/169383/The-Time-Complexity-of-The-Brute-Force-Method-Should-Be-O(2n)-and-Prove-It-Below

The Time Complexity of The Brute Force Method Should Be O(2^n) and Prove It Below - LeetCode Discuss

상기와 같은 취지를 바탕으로 2가지 방식으로 Trie형 프로그램을 만들어 보았다.

• BFS
• DFS 

Trie형은 불필요 했던거 같은데 혹시 궁금하면 참고 바란다.

//노드 정의
class Node {
    constructor(val) {
        this.val = val;
        this.next = new Map();
        this.end = false;
    }
}

var wordBreak = function(s, wordDict) {
	//Trie 루트 노드
    let root = new Node('');
    let dp = new Map(); // Trie 조회 결과 DP
    let dpDfs = new Map(); // word 조회 결과 DP

    //Trie 생성
    wordDict.forEach(word => buildWordsMap(word));

//BFS를 통한 모든 경우 조회
    // BFS -> n^n
    // let queue = new Array();
    // queue.push(s);

    // while (queue.length) {
    //     let curString = queue.shift();
    //     if(curString == '') return true;
    //     let nextPositions = searchWord(curString);
    //
    //     nextPositions.forEach(position => {
    //         queue.push(curString.slice(position+1));
    //     });
    // }

    //DFS를 통한 word Memorization
    return dfs(s);


// DFS 조회
    function dfs(word){
        if(dpDfs.has(word)){
            return dpDfs.get(word);
        }
        if(word == '') return true;

        let arrs = searchWord(word);

        for (let i = 0; i < arrs.length; i++) {
            let position = arrs[i];
            if(dfs(word.slice(position+1))){
                dpDfs.set(word,true);
                return true;
            }
        }

        dpDfs.set(word,false);
        return false;
    }


// Trie 조회
    function searchWord(word){
        if(dp.has(word)){
            return dp.get(word);
        }
        let origin = word;
        let node = root;
        let result = [];
        let count = 0;
        while (node.next.has(word.charAt(0))) {
            node = node.next.get(word.charAt(0));
            word = word.slice(1);
            if (node.end) {
                result.push(count);
            }
            count++;
        }
        dp.set(origin, result);
        return result;
    }

// Trie 생성
    function buildWordsMap(word){
        let node = root;

        while(0 < word.length){
            if(!node.next.has(word.charAt(0))){
                node.next.set(word.charAt(0), new Node(word.charAt(0)));
            }
            node = node.next.get(word.charAt(0));
            word = word.slice(1);
        }
        node.end = true;
    }

};

처음에 BFS를 이용해서 word를 찾는 방법을 만들어 보았는데,

이경우는 Memorization이 불가능 해서 DFS로 다시 만들어서 Memorization처리 했다.

 

최근에 새삼스럽게 이 문제를 다시 풀어 봤다.

방법은 동일 하긴 한데 코드는 조금 달라서 여기에 추가한다. (물론 풀때는 이 문제 풀었던거 기억이 안나서 난감 ㅠㅠ)

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function(s, wordDict) {
    let dictMap = new Map();
    let wordsMap = new Map();
    let dp = new Array(s.length).fill(null);
    
    for(const word of wordDict){
        buildNode(word);
    }
    
    // console.log(dp);
    return helper(s,0);

    function helper(str,position){
        if(dp[position] !== null) return dp[position];
        if(wordsMap.has(str)) return dp[position] = true;

        const arr = journeyNode(str);
        for(let idx of arr){
            if(helper(str.substring(idx+1),position + idx + 1)) return dp[position] = true;
        }
        return dp[position] = false;
    }
    
    
    function journeyNode(str){
        let wordMap = dictMap;
        let result = new Array();
        let breakWord = '';
        
        for(let i = 0; i < str.length; i++){
            const char = str.charAt(i);
            breakWord += char;
            if(wordMap.has(char)){
                wordMap = wordMap.get(char);
                if(wordsMap.has(breakWord)){
                    result.push(i);
                }
            } else {
                break;
            }
        }
        
        return result;
    }
    
    function buildNode(word){
        wordsMap.set(word,true);
        let wordMap = dictMap;
        
        for(let i = 0; i < word.length; i++){
            const char = word.charAt(i);
            if(!wordMap.has(char)){
                wordMap.set(char, new Map());
            }
            wordMap = wordMap.get(char);
        }
    }
};