程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> leetcode筆記:Word Pattern

leetcode筆記:Word Pattern

編輯:C++入門知識

leetcode筆記:Word Pattern


一. 題目描述

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.

Examples:
pattern = "abba", str = "dog cat cat dog" should return true.
pattern = "abba", str = "dog cat cat fish" should return false.
pattern = "aaaa", str = "dog cat cat dog" should return false.
pattern = "abba", str = "dog dog dog dog" should return false.

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

二. 題目分析

題目的大意是,給出一組模式(pattern)和一個字符串(str),判斷字符串是否與模式相匹配,並給出了幾個例子。

題目提到,模式pattern僅由小寫字母構成,而字符串str中每個單詞均被單個空格字符隔開,且字符串中每個單詞都由小寫字母構成(這種設定可以少考慮很多邊界條件);模式pattern和字符串str的前後都不包含多余的空格;且模式pattern中的每個字母必須匹配一個字符串str中長度至少為1的單詞。

容易想到的是,使用Map來解決這個問題。

於是乎,定義一個map,每遇到一個新的模式,以模式為key,將對應的單詞存入map;遇到map裡已有的模式,檢查當前str的單詞是否與map記載模式所對應的value值相同,只要出現不同,直接返回false

這種判斷方法可以解決:pattern = "abba", str = "dog cat cat fish"這種情況。

但是,只使用一個map無法判斷這種情況:pattern = "abba", str = "dog dog dog dog",一開始a作為一個新模式,被存入map,到了第二次迭代,b作為一個新模式,也被存入mapdog被分配到兩個不同的模式,顯然這是不對的。

為了解決這個問題,需要兩個map。另一個map2用於記載單詞與模式的對應關系。

總的來說,map用於記載模式到單詞的對應關系,但可能出現多個模式對應到同個單詞的情形。

而map2用於記載單詞到模式的對應關系,在判斷中同時加入對兩個map的判斷,才可以分辨所有情況。

三. 示例代碼

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        unordered_map map; // 作用是防止出現單詞不同但模式相同的情況
        unordered_map map2; // 作用是防止出現模式不同但單詞同名的情況
        vector vec; // 存放逐個單詞
        // 以下操作分割str為多個單詞
        for (int i = 0, j = 0; i < str.size(); ++i)
        {
            if (i == str.size() - 1)
            {
                string temp = str.substr(j, i - j + 1);
                vec.push_back(temp);
            }
            if (str[i] == ' ')
            {
                string temp = str.substr(j, i - j);
                vec.push_back(temp);
                j = i + 1;
            }
        }

        if (pattern.size() != vec.size()) return false;

        for (int i = 0; i < pattern.size(); ++i)
        {
            // 當前模式未出現,且對應的單詞也未出現,才將鍵值對存入表
            if (map.find(pattern[i]) == map.end() && map2.find(vec[i]) == map2.end())
            {
                map.insert(make_pair(pattern[i], vec[i]));
                map2.insert(make_pair(vec[i], pattern[i]));
            }
            else if (map[pattern[i]] != vec[i]) 
                return false;
        }

        return true;
    }
};

四. 小結

思路簡單的一道題,但實現起來還是要花點時間,而且需要注意一些細節問題。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved