程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LeetCode139:Word Break

LeetCode139:Word Break

編輯:關於C++

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< i都有關系,即A[i]與前A[]中的前i-1項都有關系,具體為:

如果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& wordDict) {
        int length=s.size();
        int *A=new int[length]();
        for(int i=0;i=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 &wordDict)
        {
            string str=s.substr(first,last-first+1);
            if(wordDict.count(str))
                return 1;
            else
                return 0;
        }

};

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved