2017阿里C++研發工程師-校招-單詞匹配 - acm1314－IT工程師數位筆記本

文章出處

題目描述

給一個字符串，然后給一個字典。把字符串分解成字典里的單詞組成的句子，請輸出所需空格最少的方案。并輸出該方案。

樣例

例如：字符串為： 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;
}