[leetcode题解] 139.单词拆分-Tire+bfs搜索题

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明:

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1:

输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。
示例 2:

输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
输出: true
解释: 返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。
     注意你可以重复使用字典中的单词。
示例 3:

输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
输出: false

【english】

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
Example 1:

Input: s = “leetcode”, wordDict = [“leet”, “code”]
Output: true
Explanation: Return true because “leetcode” can be segmented as “leet code”.
Example 2:

Input: s = “applepenapple”, wordDict = [“apple”, “pen”]
Output: true
Explanation: Return true because “applepenapple” can be segmented as “apple pen apple”.
             Note that you are allowed to reuse a dictionary word.
Example 3:

Input: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
Output: false

题目的意思是给一个单词词典,包含若干非空单侧,然后给一个字符串,需要判断该字符串是否可以由词典中的

若干单词通过收尾相接拼出来。

比如给定词典包括两个单词 [“leet”, “code”] 则字符串“leetcodecodeleet” 可以由词典中的单词拼出来。

解题思路:

涉及到词典中单词匹配,首相想到匹配可以直接建一棵tire tree(字典树)。

然后需要单词的匹配,一层一层的往后找,知道能匹配的字符串的结尾,我想到的方法是使用广度优先搜索算法。

在队列中存储可以通过词典拼出字符串的下标,然后对于每个下标,出队列后,再进行所有词典的拼接(因为词典可以重复使用),其实该题目可以变种为所有词典只能使用一次(这个就比较难了)

直接这样写的话为超时,这种方式下,可能会有大量的下标重复,从而重复搜索,分析一下可以知道,相同下标我们只需要以它为起始坐标向后搜索一次即可。

所以,可以使用一个bool数组标记一下,哪些下标已经加入过队列了,从而无需重复加入。这样优化后可以AC。

AC代码如下:

    struct tire_node
{
    struct tire_node *nodes[27];
    bool is_leaf;
    int level;
};

class Solution {
public:
    /* 凌风技术站,更多原创leetcode题解 */
    bool wordBreak(string s, vector<string>& wordDict) {
        queue<int> que;
        int idx;

        init_tire(wordDict);
        que.push(0);
        while (!que.empty()) {
            idx = que.front();
            if (idx == s.length()) {
                return true;
            }
            que.pop();
            find(&tire, s, idx, s.length(), que);
        }
        return false;
    }

private:
    struct tire_node tire;
    bool hs[2000] = {0};

    void find(struct tire_node *node, string word, int idx, int len, queue<int>& que)
    {
        int pos;

        if (node == NULL || idx >= len) {
            return;
        }
        
        pos = word[idx] - 'a';
        if (node->nodes[pos] == NULL) {
            return;
        }

        if (node->nodes[pos]->is_leaf) {
            if (!hs[idx + 1]) {
                hs[idx + 1] = true;
                que.push(idx + 1);
            }
        }

        find(node->nodes[pos], word, idx + 1, len, que);
    } 
    void insert(string word, int len, int idx, struct tire_node *node, int level)
    {   
        int pos;

        if (node == NULL) {
            return;
        }

        if (idx >= len) {
            node->is_leaf = true;
            node->level = level;
            return;
        }

        pos = word[idx] - 'a';
        if (node->nodes[pos] == NULL) {
            node->nodes[pos] = (struct tire_node *)calloc(1, sizeof(struct tire_node));
        }

        insert(word, len, idx + 1, node->nodes[pos], level + 1);
    }
    void init_tire(vector<string> &words) 
    {
        int i;

        for (i = 0; i < words.size(); i++) {
            insert(words[i], words[i].length(), 0, &tire, 0);
        }
    }
};

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解] 139.单词拆分-Tire+bfs搜索题

本文链接地址:https://www.iaccepted.net/algorithm/leetcode/254.html

相关文章