最近刷到两道类似的题目:
它们都是一个双向映射问题,思路也比较简单,都可以使用两个 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 方法上死磕,总想找到简单的分割的方法。却没去考虑针对这个问题,使用简单的两个指针来截取每个单词。
这也是许多题目会让人产生的一个想法,它们获取是不同的题型,但却可能会用到类似的一些思路。比如什么 双指针、快慢指针、滑动窗口、队列、栈、递归……
只有将各个技巧熟练掌握,熟知其应用场景,才能在复杂的问题中找到思路。
仍需努力啊!