word-break

1348 단어 Leetcode
[제목 설명] Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.For example, given s =“leetcode”, dict =[“leet”, “code”]. Return true because"leetcode"can be segmented as"leet code".
[문제풀이 사고방식] 만약에 한 단어에 하나의 분해 방법이 존재하고 분해된 모든 블록이 사전에 있다면 반드시 이러한 조건을 만족시켜야 한다. 이 단어의 마지막 분할점에 대해 이 분할점에서 단어의 끝까지 구성된 문자열은 하나의 단어이고 이 분할점에서 단어의 시작까지 구성된 문자열도 분해할 수 있다.그래서 이 조건을 충족시키기만 하면 우리는 이 긴 문자열도 분해할 수 있다는 것을 확신할 수 있다.그래서 우리는 검증을 기다리는 문자열의 길이를 외부 순환으로 제어하고 내부 순환으로 이러한 분할점을 찾아 문자열을 하나의 단어와 같은 분해 가능한 하위 문자열로 나눌 수 있다.또한, 우리는 문자열의 길이가 증가할 때 분해할 수 있는 상황을 수조로 기록하여 나중에 사용할 수 있도록 하고, 중복 계산을 피한다.
[고사 내용] 동태적 기획, 심도 있는 검색
class Solution {
public:
    bool wordBreak(string s, unordered_set &dict) {
        //dp[i]: s[0...i] can be egemented in dict
        //dp[i] = dp[0][k] && d[k][i]
        int len = s.length();
        vector dp(len,false);
        for(int i = 0; i < len; i++){
            if(dict.find(s.substr(0,i+1))!=dict.end()) dp[i]=true;//substr(  ,  )
            for(int j = 1; j <= i; j++){
                if((dict.find(s.substr(j,i-j+1))!=dict.end()) && dp[j-1]) 
                    dp[i]=true;
            }
        }
        return dp[len-1];
    }
};

좋은 웹페이지 즐겨찾기