2015年1月

该系列主要总结了使用C++来实现各种设计模式,并结合实际的案例来分析如何使用,以及在什么场合下使用设计模式。以下是该系列所有文章的链接。希望对大家有帮助。

C++设计模式——简单工厂模式
C++设计模式——工厂方法模式
C++设计模式——抽象工厂模式
C++设计模式——单例模式
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".

题目来自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;
}

- 阅读剩余部分 -