​LeetCode刷题实战291:单词规律II

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 单词规律II,我们先来看题面:
https://leetcode-cn.com/problems/word-pattern-ii/

Given a pattern and a string str, find if strfollows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty substring in str.

给你一种规律 pattern 和一个字符串 str,请你判断 str 是否遵循其相同的规律。

这里我们指的是 完全遵循,例如 pattern 里的每个字母和字符串 str 中每个 非空 单词之间,存在着双向连接的对应规律。


示例


示例1:
输入: pattern = "abab", str = "redblueredblue"
输出: true

示例2:
输入: pattern = "aaaa", str = "asdasdasdasd"
输出: true

示例3:
输入: pattern = "aabb", str = "xyzabcxzyabc"
输出: false
 
提示:
你可以默认 pattern 和 str 都只会包含小写字母。


解题

https://www.cnblogs.com/grandyang/p/5325761.html

这道题是之前那道 Word Pattern 的拓展,之前那道题词语之间都有空格隔开,这样可以一个单词一个单词的读入,然后来判断是否符合给定的特征,而这道题没有空格了,那么难度就大大的增加了。

因为我们不知道对应的单词是什么,所以得自行分开,可以用回溯法来生成每一种情况来判断,这里还是需要用 HashMap 来建立模式字符和单词之间的映射,还需要用变量p和r来记录当前递归到的模式字符和单词串的位置,在递归函数中,如果p和r分别等于模式字符串和单词字符串的长度,说明此时匹配成功结束了,返回 ture,反之如果一个达到了而另一个没有,说明匹配失败了,返回 false。如果都不满足上述条件的话,取出当前位置的模式字符,然后从单词串的r位置开始往后遍历,每次取出一个单词,如果模式字符已经存在 HashMap 中,而且对应的单词和取出的单词也相等,那么再次调用递归函数在下一个位置,如果返回 true,那么就返回 true。

反之如果该模式字符不在 HashMap 中,要看有没有别的模式字符已经映射了当前取出的单词,如果没有的话,建立新的映射,并且调用递归函数,注意如果递归函数返回 false 了,要在 HashMap 中删去这个映射,参见代码如下:


class Solution {
public:
    bool wordPatternMatch(string pattern, string str) {
        unordered_map<char, string> m;
        return helper(pattern, 0, str, 0, m);
    }
    bool helper(string pattern, int p, string str, int r, unordered_map<char, string> &m) {
        if (p == pattern.size() && r == str.size()) return true;
        if (p == pattern.size() || r == str.size()) return false;
        char c = pattern[p];
        for (int i = r; i < str.size(); ++i) {
            string t = str.substr(r, i - r + 1);
            if (m.count(c) && m[c] == t) {
                if (helper(pattern, p + 1, str, i + 1, m)) return true;
            } else if (!m.count(c)) {
                bool b = false;
                for (auto it : m) {
                    if (it.second == t) b = true;
                }
                if (!b) {
                    m[c] = t;
                    if (helper(pattern, p + 1, str, i + 1, m)) return true;
                    m.erase(c);
                }
            }
        }
        return false;
    }
};


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:
LeetCode1-280题汇总,希望对你有点帮助!
LeetCode刷题实战281:锯齿迭代器
LeetCode刷题实战282:给表达式添加运算符
LeetCode刷题实战283:移动零
LeetCode刷题实战284:顶端迭代器
LeetCode刷题实战285:二叉搜索树中的顺序后继
LeetCode刷题实战286:墙和门
LeetCode刷题实战287:寻找重复数
LeetCode刷题实战288:单词的唯一缩写
LeetCode刷题实战289:生命游戏
LeetCode刷题实战290:单词规律


​LeetCode刷题实战291:单词规律II

原创文章,作者:栈长,如若转载,请注明出处:https://www.cxyquan.com/12386.html

发表评论

登录后才能评论

联系我们

400-800-8888

在线咨询:点击这里给我发消息

邮件:admin@example.com

工作时间:周一至周五,9:30-18:30,节假日休息