最近刷到两道类似的题目:

它们都是一个双向映射问题,思路也比较简单,都可以使用两个 map 来互相保存对对方的映射。如果发现不一致则说明不满足要求。

但每次做题的时候都感觉思路打不开。比如 205 号题做过之后,遇到 290 号自然会想到这个办法。但 290 给出的第二个字符串是单词,用空格分割。

其它语言一般都有 split 函数,将字符串分割成数组,可是 C++ 没有类似的函数。作为没有特别熟悉 C++ 的用户,看到网上给的许多方法都觉得有些复杂。

而后看了官方给出的解答:

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        unordered_map str2ch;
        unordered_map ch2str;
        int m = str.length();
        int i = 0;
        for (auto ch : pattern) {
            if (i >= m) {
                return false;
            }
            int j = i;
            while (j < m && str[j] != ' ') j++;
            const string &tmp = str.substr(i, j - i);
            if (str2ch.count(tmp) && str2ch[tmp] != ch) {
                return false;
            }
            if (ch2str.count(ch) && ch2str[ch] != tmp) {
                return false;
            }
            str2ch[tmp] = ch;
            ch2str[ch] = tmp;
            i = j + 1;
        }
        return i >= m;
    }
};
/**
作者:LeetCode-Solution
链接:https://leetcode.cn/problems/word-pattern/solution/dan-ci-gui-lu-by-leetcode-solution-6vqv/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
*/

就觉得自己格局小了。遇到这样的问题就在 split 方法上死磕,总想找到简单的分割的方法。却没去考虑针对这个问题,使用简单的两个指针来截取每个单词。

这也是许多题目会让人产生的一个想法,它们获取是不同的题型,但却可能会用到类似的一些思路。比如什么 双指针、快慢指针、滑动窗口、队列、栈、递归……

只有将各个技巧熟练掌握,熟知其应用场景,才能在复杂的问题中找到思路。

仍需努力啊!

Tagged in: