[Leetcode] 139. Word Break

 

 

해설 코드 출처

https://leetcode.com/problems/word-break/discuss/1399968/C-Implemented-in-C-with-dynamic-programming%EF%BB%BF

Identifying the Problem

주어진 s를 wordDict상의 단어들로 만들 수 있는지 판단해

가능하면 true , 불가능하다면 false를 return한다.

Organizing thoughts

MAIN IDEA s의 길이가 n일 때

0, 0~1, 0~2,,, 0~n-1 ,0~n 를 worddict으로 만들 수 있는지 판단한다.

 

예를 들어 s 가 leetcode 면,

l를 worddict으로 만들 수 있는지

le를 worddict으로 만들 수 있는지

lee를 worddict으로 만들 수 있는지

leet를 worddict으로 만들 수 있는지

leetc를 worddict으로 만들 수 있는지

leetco를 worddict으로 만들 수 있는지

leetcod를 worddict으로 만들 수 있는지

leetcode를 worddict으로 만들 수 있는지 검사한다.

 

그리고 leetcode는 leet를 이미 worddict으로 만들 수 있기 때문에, 

code만 worddict으로 만들 수 있는지 판단한다.

Sourcecode

/*본인이 작성한 코드가 아님*/

bool wordBreak(char* s, char** wordDict, int wordDictSize)
{
    if(wordDict == NULL || wordDictSize==0 || s== NULL) 
    worddict이나, s 중//하나라도 아무것도 없으면 false return
    {
        return false;
    }
    
    int len = strlen(s) + 1;
    
    bool *hit = calloc(len, sizeof(bool)); //dp 생성
    
    hit[0] = true; //아무것도 없는거는 dict없어도 만들 수 있으니 true
    			   //초기값 설정 
                   
    for (int i = 0; i < len; i++) { //s 전체 길이만큼 탐색
        for (int j = 0; j < wordDictSize; j++) { //worddict 검사
            if(hit[i]) { //처음은 초기값 true이므로 검사
                
                int wordLen = strlen(wordDict[j]);

                char str[wordLen+1];
                strncpy(str, s+i, wordLen);
                str[wordLen]='\0';
                
                if(strcmp(str, wordDict[j]) == 0) {
                    hit[i+wordLen] = true; 
                    //worddict이 들어가니 탐색index + 단어 길이 dp[index]는 true
                }
            }
        }
    }
    return hit[len-1]; //s의 dp결과를 return
}

Mistake

뭔가 계속 이어져 가는데, 그 이어짐을 어떻게 이을지 답답했다.

나중에서야 dp로 풀면 간단했음을 알았다..