2017阿里C++研发工程师-校招-单词匹配

题目描述

给一个字符串，然后给一个字典。把字符串分解成字典里的单词组成的句子，请输出所需空格最少的方案。并输出该方案。

样例

例如：字符串为： str="ilikealibaba", 字典为dict= {"i", "like", "ali", "ba", "alibaba", "baba"}

输入：

ilikealibaba

6

i

like

ali

ba

alibaba

baba

输出：

i like alibaba

解题思路：

空格最少，很显然用BFS应该可以做。不过状态转移的时候需要写个小函数，另外由于需要打印路径，所以要记录一下路径。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <vector>

#include <string>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <unordered_set>

#include <unordered_map>

#include <algorithm>

#include <stdexcept>

#include <cstring>

using namespace std;

struct Node

{

	string word;     // 当前匹配过的单词

	int pos;            // 记录下一个要匹配的位置

	string path;      // 记录路径

}; 

int matchW(const string& str, int pos, const string word)

{

	for(int i = 0; i < word.size(); i++)

	{

		if(pos >= str.size())

			return -1;

		if(str[pos++] != word[i])

			return -1;

	}

	return pos;

}

void mincut(const string& str, const set<string>& dict)

{

	if(str.size() == 0)

	{

		printf("n/a\n");

		return;

	}

	queue<Node> qu;

	for(auto it : dict)

	{

		int tmp = matchW(str, 0, it);

		if(tmp != -1)        // 该单词是否能匹配

		{

			Node tt;

			tt.word = it;

			tt.pos = tmp;

			tt.path += it;

			qu.push(tt);

		}

	}

	while(!qu.empty())

	{

		int len = qu.size();

		while(len--)

		{

			Node tt = qu.front();

			qu.pop();

			if(tt.pos == str.size())    // 已匹配完成

			{

				cout << tt.path << endl;      // 打印路径

				return;

			}

			for(auto it : dict)

			{

				int tmp = matchW(str, tt.pos, it);

				if(tmp != -1)

				{

					Node gg;

					gg.word = it;

					gg.pos = tmp;

					gg.path = tt.path + " " + it;

					qu.push(gg);

				}

			}

		}

	}

	printf("n/a\n");

}

int main(int argc, const char * argv[])

{

    string strS;

    string dictStr;

    int nDict;

    set<string> dict;

    cin>>strS;

    cin>>nDict;

    for (int i = 0; i < nDict; i++)

    {

        cin>>dictStr;

        dict.insert(dictStr);

    }

    mincut(strS, dict);

    return 0;

}

巴特西

2017阿里C++研发工程师-校招-单词匹配

题目描述

样例

解题思路：

最新文章

热门文章