iT邦幫忙

2024 iThome 鐵人賽

0
佛心分享-刷題不只是刷題

刷經典 LeetCode 題目系列 第 75

經典LeetCode 290. Word Pattern

  • 分享至 

  • xImage
  •  

題目:

我們需要判斷給定的字串 pattern 是否與字串 s 遵循相同的模式。
具體來說,每個 pattern 中的字元應唯一地對應到 s 中的單詞,並且這種對應應該是雙向的。

範例:

Input: pattern = "abba", s = "dog cat cat dog"
Output: true

Input: pattern = "abba", s = "dog cat cat fish"
Output: false

Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false

解題思路

解題重點思路在雙向映射,用兩個 unordered_map,一個是紀錄 pattern 到 word 的映射,另外一個則是紀錄word 到 pattern 的映射,

用 stringstream 來分割空白,可以方便得到每個 word,

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        vector<string> words;
        stringstream ss(s);
        string word;
        while (ss >> word) {
            words.push_back(word);
        }

        if (pattern.size() != words.size()) {
            return false;
        }

        unordered_map<char, string> patternToWord;
        unordered_map<string, char> wordToPattern;
        
        for (int i = 0; i < pattern.size(); i++) {
            char p = pattern[i];
            string w = words[i];
            if (patternToWord.count(p) && patternToWord[p] != w)
                return false;
            
            if (wordToPattern.count(w) && wordToPattern[w] != p)
                return false;

            patternToWord[p] = w;
            wordToPattern[w] = p;
        }
        return true;
    }
};

參考:
#290. Word Pattern


上一篇
經典LeetCode 205. Isomorphic Strings
下一篇
經典LeetCode 112. Path Sum
系列文
刷經典 LeetCode 題目80
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言