精品麻豆一区二区国产明星,黄色一级片毛,亚洲色综合,黑人激情操逼,视频在线99,翔田千里久久,特级西西444Ww高清大胆,久久夜色精品网站

算法的重要性，我就不多說(shuō)了吧，想去大廠(chǎng)，就必須要經(jīng)過(guò)基礎(chǔ)知識(shí)和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號(hào)后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問(wèn)題叫做 單詞規(guī)律，我們先來(lái)看題面：

https://leetcode-cn.com/problems/word-pattern/

Given a pattern and a string s, find if s 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 s.

給定一種規(guī)律 pattern 和一個(gè)字符串 str ，判斷 str 是否遵循相同的規(guī)律。

這里的遵循指完全匹配，例如， pattern 里的每個(gè)字母和字符串 str 中的每個(gè)非空單詞之間存在著雙向連接的對(duì)應(yīng)規(guī)律。

示例

示例1:

輸入: pattern = "abba", str = "dog cat cat dog"
輸出: true

示例 2:

輸入:pattern = "abba", str = "dog cat cat fish"
輸出: false

示例 3:

輸入: pattern = "aaaa", str = "dog cat cat dog"
輸出: false

示例 4:

輸入: pattern = "abba", str = "dog dog dog dog"
輸出: false

說(shuō)明:
你可以假設(shè) pattern 只包含小寫(xiě)字母， str 包含了由單個(gè)空格分隔的小寫(xiě)字母。

解題

方法一：哈希表

在本題中，我們需要判斷字符與字符串之間是否恰好一一對(duì)應(yīng)。即任意一個(gè)字符都對(duì)應(yīng)著唯一的字符串，任意一個(gè)字符串也只被唯一的一個(gè)字符對(duì)應(yīng)。在集合論中，這種關(guān)系被稱(chēng)為「雙射」。

想要解決本題，我們可以利用哈希表記錄每一個(gè)字符對(duì)應(yīng)的字符串，以及每一個(gè)字符串對(duì)應(yīng)的字符。然后我們枚舉每一對(duì)字符與字符串的配對(duì)過(guò)程，不斷更新哈希表，如果發(fā)生了沖突，則說(shuō)明給定的輸入不滿(mǎn)足雙射關(guān)系。

在實(shí)際代碼中，我們枚舉pattern 中的每一個(gè)字符，利用雙指針來(lái)均攤線(xiàn)性地找到該字符在 str 中對(duì)應(yīng)的字符串。每次確定一個(gè)字符與字符串的組合，我們就檢查是否出現(xiàn)沖突，最后我們?cè)贆z查兩字符串是否比較完畢即可。

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        unordered_map<string, char> str2ch;
        unordered_map<char, string> 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;
    }
};