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

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".

基本思路:

動態規劃。

數組 dp[i],表示第i個字符以前是否可以分隔成單詞。 i 從0開始。

已知dp[0..i]時,求dp[i+1],則需要償試,s[k..i], 0<=k <=i, 進行償試。

 

在leetcode上實際執行時間為12ms。

 

 

class Solution {
public:
    bool wordBreak(string s, unordered_set& wordDict) {
        vector dp(s.size()+1);
        dp[0] = true;
        for (int i=1; i<=s.size(); i++) {
            for (int j=0; j

 

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