【编程题】2018阿里编程题题一

转化为最短路径搜索：

将D中存储的词看为一条路径：如”like”表示“ilikealibaba”中存在一条从S[1]: “l”直接到S[5]: “a”的路径。

则最少空格数的解就是从S[0]走到S[n]最短路径的解。

测试样例中存在两条路径：

1: S[0]->S[1]->S[5]->S[7]->S[12]

2: S[0]->S[1]->S[5]->S[12]

最短路径使用BFS

#include <stdio.h>
#include <vector>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <string>
#include <set>
#include <regex>
#include <queue>
using namespace std;
//#define debug_
void mincut(const string& str, const set<string>& dict)
{
    vector<vector<int>> path_map(str.size());
    vector<int> cost(str.size()+1,99999);
    int strSize = str.size();

    for (auto i = 0; i < str.size();++i)
    {
        for (auto iter = dict.begin(); iter != dict.end();iter++)
        {
            if (str.substr(i,(*iter).size()) == *iter)
            {
                path_map[i].push_back(i+(*iter).size());
            }
        }
    }

    queue<int> que;
    que.push(0);
    cost[0] = 0;
    while (!que.empty())
    {
        int s = que.front();
        que.pop();
        for (auto i = 0; i < path_map[s].size();++i)
        {
            if (cost[s]+1<cost[path_map[s][i]])
            {
                if (path_map[s][i] != strSize)//不是终点
                {
                    que.push(path_map[s][i]);
                }
                cost[path_map[s][i]] = cost[s] + 1;
            }
        }
    }
    int cur_index(strSize);
    vector<string> print_vec;
    if (cost[strSize] == 99999)
    {
        cout <<"n/a";
        return;
    }
    for (auto i = strSize; i >= 0;--i)
    {
        if (cost[i] + 1 == cost[cur_index])
        {
            string tmp = str.substr(i, cur_index-i);
            print_vec.push_back(tmp);
            cur_index = i;
        }
    }
    for (auto iter = print_vec.rbegin(); iter != print_vec.rend();iter++)
    {
        cout << *iter << " ";
    }
}


int main(int argc, const char * argv[])
{
    string strS;
    string dictStr;
    int nDict;
    set<string> dict;
#ifdef debug_
    strS = "ilikealibaba";
    dict.insert("i");
    dict.insert("like");
    dict.insert("ali");
    dict.insert("liba");
    dict.insert("baba");
    dict.insert("alibaba");
#else

    cin >> strS;
    cin >> nDict;
    for (int i = 0; i < nDict; i++)
    {
        cin >> dictStr;
        dict.insert(dictStr);
    }
#endif
    mincut(strS, dict);

    return 0;
}