[Leetcode]290. Word Pattern(C++)

题目描述

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

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

例子

例子 1

Input: pattern = “abba”, str = “dog cat cat dog” Output: true

例子 2

Input: pattern = “abba”, str = “dog cat cat fish” Output: false

例子 3

Input: pattern = “aaaa”, str = “dog cat cat dog” Output: false

例子 4

Input: pattern = “abba”, str = “dog dog dog dog” Output: false

Note

You may assume pattern contains only lowercase letters, and str contains lowercase letters that may be separated by a single space.

解题思路

首先从字符串中获取单词很简单，通过一个指针以空格为分界线遍历即可。这里考虑到需要建立字母和单词之间的对应关系，很容易想到使用哈希表。同时注意对应是关系是双向的，意味着单词->字母和字母->单词都需要一一对应，因此需要建立两个哈希表存储两边对应关系。同时因为对应关系都两侧都必须非空，因此还要判断 pattern 中的字符和 str 中的单词数是否一致，可以在遍历完 pattern 后判断遍历 str 的指针是否已指向末尾即可，代码如下：

#include <string>
#include <unordered_map>

class Solution {
public:
    bool wordPattern(std::string pattern, std::string str) {
        std::unordered_map<char, std::string> dist;
        std::unordered_map<std::string, char> rev_dist;
        int ptr = 0;
        for (int i = 0; i < pattern.length(); i++) {
            char key = pattern[i];
            std::string word = "";
            while (ptr < str.length() && str[ptr] == ' ') ptr++;
            while (ptr < str.length() && str[ptr] != ' ') {
                word += str[ptr];
                ptr++;
            }
            if (word.empty()) return false;

            if (dist.find(key) == dist.end()) {
                dist[key] = word;
            } else if (dist[key] != word) {
                return false;
            }
            if (rev_dist.find(word) == rev_dist.end()) {
                rev_dist[word] = key;
            } else if (rev_dist[word] != key) {
                return false;
            }
        }
        if (ptr != str.length()) return false;

        return true;
    }
};

时间复杂度: O(n) n 为 str 长度
空间复杂度: O(1) 虽然单词有组合有无数种，但是字母数量是常数