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

题目来自Leeocode:https://oj.leetcode.com/problems/word-break/

最容易想到的方法是递归算法,先判断字符串前部分是否构成单词,若构成再按照同样方法判断后半部分,写成数学形式更易理解(自顶而上):
(1)设f[1,n]表示字符串1~n位置是否能构成单词,f[1,n]即为最终解;
(2)f[1,n]可以分解为f[1,i]&f[i+1,n],1<=i<n,即f[1,n]=f[1,i]&f[i+1,n];

一、递归算法(深搜)
递归算法每次判别f[1,i]是否输入unodered_set(dict),一旦判断为单词,分解为小规模问题f[i+1,n]。但是递归算法效率很低,提交时Time Limited

bool isWord(int k,string s,unordered_set<string> &dict)
{
    if(k==s.length())
        return true;
    for(int i=k;i<s.length();i++)
    {
        string str;
        for(int j=k;j<=i;j++)
            str.push_back(s[j]);

        if(dict.find(str)!=dict.end())
            if(isWord(i+1,s,dict))
                return true;
    }
    return false;
}

bool wordBreak1(string s, unordered_set<string> &dict) 
{
    for(int i=0;i<s.length();i++)
    {
        string str;
        for(int j=0;j<=i;j++)
            str.push_back(s[j]);

        if(dict.find(str)!=dict.end())
            if(isWord(i+1,s,dict))
                return true;
    }
    return false;
}

二、动态规划(DP)
动态规划是自底而上的,这里可以使用一维数组wordB[](长度为length+1)标记子串是否可以分割,例如wordB[i]表示长度为i的子串是否可以分割,wordB[length]为最终结果。DP形式的代码很简洁,同时减少了不必要的比较,当能够判断子串是否成立后立即跳出循环。

// 初始状态:wordB[0]=true;
bool wordBreak(string s, unordered_set<string> &dict) 
{  
    vector<bool> wordB(s.length() + 1, false);  
    wordB[0] = true;  
    for (int i = 1; i < s.length() + 1; i++) 
    {  
        for (int j = i - 1; j >= 0; j--) 
        {  
            if (wordB[j] && dict.find(s.substr(j, i - j)) != dict.end()) 
            {  
                wordB[i] = true;  
                break;   
            }  
        }  
    }  
    return wordB[s.length()];  
} 

标签: 动态规划, 算法

评论已关闭