给定字符串，以及一个字典，判断字符串是否能够拆分为字段中的单词。例如，字段为{hello，world}，字符串为hellohelloworld，则可以拆分为hello,hello,world，都是字典中的单词。 题目来源：http://mp.weixin.qq.com/mp/appmsg/show?__biz=MjM5ODIzNDQ3Mw==&appmsgid=10000306&itemidx=1&sign=45327171923a822ffd8727e6983727c2 原题解是动态规划，本代码是备忘录式的递归法。

is_in_dict.cpp

#include <iostream>
#include <string>
#include <unordered_map> // need c++11 or c++0x

using namespace std;

unordered_map<string, bool> dict;
unordered_map<string, bool> memo;

inline bool is_in_dict_pri(const string& word)
{
    return dict.find(word) != dict.end();
}

inline bool is_in_memo(const string& word)
{
    return memo.find(word) != memo.end();
}

bool is_in_dict(const string& word)
{
    if(word.size() < 1){
        return true;
    }else{
        if(is_in_memo(word)){
            return memo[word];
        }
        for(size_t i=1;i<word.size()+1;++i){
            string part_1 = word.substr(0, i);
            string part_2 = word.substr(i, word.size()-i); // note, part_2 may be empty
            if(is_in_dict_pri(part_1)
                    && is_in_dict(part_2)){
                memo[part_1] = true;
                memo[part_2] = true;
                memo[word] = true;
                return true;
            }
        }
        memo[word] = false;
        return false;
    }
}

int main()
{
    int test_num = 0;
    cin >> test_num;

    while(test_num --){
        int dic_num = 0;
        int word_num = 0;

        cin >> dic_num >> word_num;

        while(dic_num --){
            string word;
            cin >> word;
            dict[word] = true;
        }
        while(word_num --){
            string input;
            cin >> input;
            if(is_in_dict(input)){
                cout << "Yes" << endl;
            }else{
                cout << "No" << endl;
            }
        }
        dict.clear();
        memo.clear();
    }
    return 0;
}

small.in

3
2 2
hello
world
helloworld
hellohello
5 5
apple
small
take
you
shit
appleshityoutakesmall
appleappleapple
app
asdalks
appleadfassd
3 5
zilla
mozilla
tim
mmozillatimasdasd
ttim
mozilla
mozillatim
mozillazillappletimapplezillamoziillaaaaaaaaaaaaaaaaaaaaaaaaaaaa

small.out

Yes
Yes
Yes
Yes
No
No
No
No
No
Yes
Yes
No