LeetCode139:Word Break

3482 단어
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”.
동적 기획 문제를 처음 풀 때 이 문제를 열었던 기억이 나는데 그때는 생각이 없었다.현재 동적 기획의 문제가 많이 갱신되었다. 오늘 이 문제를 다시 풀 때 곧 상태와 상태 이동 방정식을 생각해냈기 때문에 말하지 않아도 약간 진보했다.A[i]를 정의하면 0에서 i로 표시된 하위 문자가 dict의 여러 단어로 분할될 수 있는지 여부를 나타냅니다.그러면 A[i]와 A[j], 0<=j 만약에 A[0]가 1이면 s에서 1부터 i까지 표시된 문자가 dict에 있는지 판단한다. 만약에 A[i]를 1로 설정하고 튀어나오지 않으면 두 번째 단계로 들어간다.
  • 만약에 A[1이 1이면 s에서 2부터 i로 끝나는 문자가 dict에 있는지 판단한다. 만약에 A[i]를 1로 설정하고 튀어나오지 않으면 두 번째 단계로 들어간다.이렇게 A[i-1] 위치까지 쭉 옮겨다니세요.위의 스트리밍 과정에서 만약에 j, A[j]=1을 스트리밍하고 j+1에서 i로 표시된 문자열이 dict에 나타나면 앞의 j 문자열이 dict의 단어로 분할되고 j+1에서 i의 문자열도 dict의 단어로 분할된다. 이렇게 하면 앞의 i문자가 dict의 단어로 분할될 수 있음을 나타낸다.

    • 실제 코드를 작성할 때 j는 i부터 거꾸로 옮겨다니기 시작하여 옮겨다니는 횟수를 줄일 수 있다.
    runtime:4ms 
    class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        int length=s.size();
        int *A=new int[length]();
        for(int i=0;i<length;i++)
        {
            for(int j=i;j>=0;j--)
            {
                if(j==i)
                {
                    A[i]=isExist(s,0,i,wordDict);
                }
                else if(A[j]==1)
                {
                    A[i]=isExist(s,j+1,i,wordDict);
                }
                if(A[i]==1)
                        break;
            }
        }

        return A[length-1]==1;

    }

        int isExist(string &s,int first,int last,unordered_set<string> &wordDict)
        {
            string str=s.substr(first,last-first+1);
            if(wordDict.count(str))
                return 1;
            else
                return 0;
        }

};
    Vue.js 뿌시기_9 (컴포넌트 심화)
    Templete literals

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage