阿里校招编程题第一题字典查询

使用字典树Trie存储

#include 
#include 
#include 
#include 
using namespace std;
class TrieNode {
public:
    TrieNode() {
        isWord = false;
        memset(next, 0, sizeof(next));
    }

    bool isWord;
    TrieNode* next[26];
};
class Trie {
public:
    Trie() {
        root = new TrieNode();
    }
    // Inserts a word into the trie.
    void insert(string word) {
        TrieNode *node = root;
        for(int i = 0; i < word.size(); i++)
        {
            int index = word[i] - 'a';
            if(node->next[index] == NULL){
                node->next[index] = new TrieNode();
            }
            node = node->next[index];
        }
        node->isWord = true;
    }
    // Returns if the word is in the trie.
    bool search(string word) {
        TrieNode *node = root;
        for(int i = 0; i < word.size(); i++)
        {
            int index = word[i] - 'a';
            if(node->next[index] == NULL)
                return false;
            node = node->next[index];
        }
        if(node->isWord)
            return true;
        else
            return false;
    }
    // Returns if there is any word in the trie
    // that starts with the given prefix.
    bool startsWith(string prefix) {
        TrieNode *node = root;
        for(int i = 0; i < prefix.size(); i++)
        {
            int index = prefix[i] - 'a';
            if(node->next[index] == NULL)
                return false;
            node = node->next[index];
        }
        return true;
    }
private:
    TrieNode* root;
};
int flag;
int minCutSteps;
vector curPath;
vector resultPath;
void copyVector(vector &src, vector &target) {
    target.clear();
    for (int i = 0; i < src.size(); i++) {
        target.push_back( src[i] );
    }
}
void mincutHelper(string &str, Trie *trie, int curIdx, int steps, vector &path) {
    if ( curIdx >= str.length() ) {
        flag = true;
        // cout << "found steps: " << steps << endl;
        if (minCutSteps > steps) {
            minCutSteps = steps;
            copyVector(path, resultPath);
        }
        return;
    }

    //start with curIdx
    for (int wordRIdx = curIdx; wordRIdx < str.length(); wordRIdx++) {
        int curStrLen = wordRIdx - curIdx + 1;
        string subStr = str.substr(curIdx, curStrLen);
        if ( !trie->startsWith(subStr) )
            break;
        else {
            if ( trie->search(subStr) ) {
                path.push_back(wordRIdx + 1);
                mincutHelper(str, trie, wordRIdx + 1, steps + 1, path);
                path.pop_back();
            }
        }
    }
}
// void showVector(vector &v) {
//     for (int i = 0; i < v.size(); i++)
//         cout << v[i] << " ";
//     cout << endl;
// }
void mincut(string &str, set& dict) {
    Trie *trie = new Trie();
    set::iterator iter;
    for (iter = dict.begin(); iter != dict.end(); iter++) {
        trie->insert( (string)*iter );
    }
    int strLen = str.length();
    flag = false;
    minCutSteps = strLen + 1;
    mincutHelper(str, trie, 0, 0, curPath);
    if (flag) {
        // cout << minCutSteps << endl;
        int startIdx = 0;
        // showVector(resultPath);
        for (int i = 0; i < resultPath.size(); i++) {
            int curLen = resultPath[i] - startIdx;
            if (startIdx > 0)
                cout << " ";
            cout << str.substr(startIdx, curLen);
            startIdx = resultPath[i];
        }
        cout << endl;
    } else {
        cout << "n/a" << endl;
    }
}
/*
ilikealibaba
6
i
like
ali
liba
baba
alibaba
*/
int main(int argc, char const *argv[])
{
    string strS;
    string dictStr;
    int nDict;
    set dict;
    cin >> strS;
    cin >> nDict;
    for (int i = 0; i < nDict; i++) {
        cin >> dictStr;
        dict.insert(dictStr);
    }
    mincut(strS, dict);
    return 0;
}

更新版本

如果strS比较长，nDict集比较少，优先采用字典存在长度迭代

#include <iostream>
#include <string>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

class TrieNode {
public:
    TrieNode() {
        isWord = false;
        memset(next, 0, sizeof(next));
    }

    bool isWord;
    TrieNode* next[26];
};

class Trie {
public:
    Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    void insert(string word) {
        TrieNode *node = root;
        for(int i = 0; i < word.size(); i++)
        {
            int index = word[i] - 'a';
            if(node->next[index] == NULL){
                node->next[index] = new TrieNode();
            }
            node = node->next[index];
        }
        node->isWord = true;
    }

    // Returns if the word is in the trie.
    bool search(string word) {
        TrieNode *node = root;
        for(int i = 0; i < word.size(); i++)
        {
            int index = word[i] - 'a';
            if(node->next[index] == NULL)
                return false;
            node = node->next[index];
        }

        if(node->isWord)
            return true;
        else
            return false;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    bool startsWith(string prefix) {
        TrieNode *node = root;
        for(int i = 0; i < prefix.size(); i++)
        {
            int index = prefix[i] - 'a';
            if(node->next[index] == NULL)
                return false;
            node = node->next[index];
        }
        return true;
    }

private:
    TrieNode* root;
};


int flag;
int minCutSteps;
vector<int> curPath;
vector<int> resultPath;
vector<int> strLenItems;

void copyVector(vector<int> &src, vector<int> &target) {
    target.clear();
    for (int i = 0; i < src.size(); i++) {
        target.push_back( src[i] );
    }
}

void mincutHelper(string &str, Trie *trie, int curIdx, int steps, vector<int> &path) {
    if ( curIdx >= str.length() ) {
        flag = true;
        // cout << "found steps: " << steps << endl;
        if (minCutSteps > steps) {
            minCutSteps = steps;
            copyVector(path, resultPath);
        }
        return;
    }



    /*
    **version 1
    //start with curIdx
    for (int wordRIdx = curIdx; wordRIdx < str.length(); wordRIdx++) {
        int curStrLen = wordRIdx - curIdx + 1;
        string subStr = str.substr(curIdx, curStrLen);
        if ( !trie->startsWith(subStr) )
            break;
        else {
            if ( trie->search(subStr) ) {
                path.push_back(wordRIdx + 1);
                mincutHelper(str, trie, wordRIdx + 1, steps + 1, path);
                path.pop_back();
            }
        }
    }
    */


    // iter with word's length
    for (int i = 0; i < strLenItems.size(); i++) {
        if ( i > 0 && strLenItems[i] == strLenItems[i - 1])
            continue;
        if ( curIdx + strLenItems[i] > str.length() )
            break;
        string subStr = str.substr(curIdx, strLenItems[i]);

        if ( !trie->startsWith(subStr) )
            break;
        else {
            if ( trie->search(subStr) ) {
                path.push_back( curIdx + strLenItems[i] );
                mincutHelper(str, trie, curIdx + strLenItems[i], steps + 1, path);
                path.pop_back();
            }
        }        
    }
}

// void showVector(vector<int> &v) {
//     for (int i = 0; i < v.size(); i++)
//         cout << v[i] << " ";
//     cout << endl;
// }

void mincut(string &str, set<string>& dict) {
    Trie *trie = new Trie();
    set<string>::iterator iter;
    for (iter = dict.begin(); iter != dict.end(); iter++) {
        trie->insert( (string)*iter );
        strLenItems.push_back( (*iter).length() );
    }
    sort(strLenItems.begin(), strLenItems.end());

    int strLen = str.length();
    flag = false;
    minCutSteps = strLen + 1;

    mincutHelper(str, trie, 0, 0, curPath);

    if (flag) {
        // cout << minCutSteps << endl;
        int startIdx = 0;
        // showVector(resultPath);
        for (int i = 0; i < resultPath.size(); i++) {
            int curLen = resultPath[i] - startIdx;
            if (startIdx > 0)
                cout << " ";
            cout << str.substr(startIdx, curLen);
            startIdx = resultPath[i];
        }
        cout << endl;
    } else {
        cout << "n/a" << endl;
    }
}

/*
ilikealibaba
6
i
like
ali
liba
baba
alibaba
*/
int main(int argc, char const *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;
}

#阿里巴巴#