[LeetCode]139.Word Break

题目

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

思路

递归

代码

/*---------------------------------------
*   日期：2015-05-07
*   作者：SJF0115
*   题目: 139.Word Break
*   网址：https://leetcode.com/problems/word-break/
*   结果：AC
*   来源：LeetCode
*   博客：
-----------------------------------------*/
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        int size = wordDict.size();
        if(size == 0){
            return false;
        }//if
        vector<bool> visited(s.size(),false);
        return helper(s,wordDict,0,visited);
    }
private:
    bool helper(string &s,unordered_set<string>& wordDict,int index,vector<bool> &visited){
        if(index >= s.size()){
            return true;
        }//if
        // 已经查看过表示行不通
        if(visited[index]){
            return false;
        }//if
        visited[index] = true;
        // 以index下标开始
        for(int i = index;i < s.size();++i){
            if(wordDict.find(s.substr(index,i - index + 1)) != wordDict.end()){
                if(helper(s,wordDict,i+1,visited)){
                    return true;
                }//if
            }//if
        }//for
        return false;
    }
};

int main() {
    Solution solution;
    string str("leetcode");
    unordered_set<string> wordDict = {"leet","co","code"};
    cout<<solution.wordBreak(str,wordDict)<<endl;
}

运行时间

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>