---
# System prepended metadata

title: 290. Word Pattern
tags: [string, Leetcode, python, c++, hash, easy]

---

###### tags: `Leetcode` `easy` `hash` `string` `python` `c++`

# 290. Word Pattern

## [題目連結:] https://leetcode.com/problems/word-pattern/description/

## 題目:
![](https://i.imgur.com/hgFrL0z.png)
![](https://i.imgur.com/aLYlA5S.png)


## 解題想法:
* 此題為判斷合法映射
    * 每個pattern中的char與s中的string需一對一映射
    * 不能一對多

* 用hash table存資訊:
    * 字典dic:
        * key: pattern's char
        * value: s's string
    * 初始需先對s做split將空格去掉
        * token=s.split(" ")
    * for i in range(len(pattern)): 進行對應
        * case1: 若字典已有紀錄當前char(pattern[i])
            * 判斷其存的value是否為當前的token[i]
                * 若不是則return false
        * case2: 字典沒有相關紀錄
            * **因為需要考慮到不能有一對多的情況**
            ex: pattern="abba", s="dog dog dog dog"
                * 在紀錄a後, dic已存 dic[a]=dog
                * 但隨後新字b紀錄, dic[b]=dog, 不可一對多
                * 所以須**先檢查所有dic中的key，其value是否已經有紀錄過當前的token**
                * 若有則會造成一對多，需直接return False
            * 若都安全，才能將dic[pattern[i]]=token[i]進行對應


## Python:
``` python=
from collections import defaultdict
class Solution(object):
    def wordPattern(self, pattern, s):
        """
        :type pattern: str
        :type s: str
        :rtype: bool
        """
        dic=defaultdict(str) #key: pattern's char; value: s's string
        token=s.split(" ")
        if len(token)!=len(pattern):
            return False
        for i in range(len(pattern)):
            #case1: 若字典已有相關紀錄
            if pattern[i] in dic:
                if dic[pattern[i]]!=token[i]:
                    return False
            #case2: 字典沒有相關紀錄
            else:
                for key in dic:
                    if dic[key]==token[i]:
                        return False
                dic[pattern[i]]=token[i]
        return True    
        
if __name__ == '__main__':
    pattern = "abba"
    s = "dog cat fish dog"
    result = Solution()
    ans = result.wordPattern(pattern,s)
    print(ans)
```

## C++:
* c++沒有split
* 需額外撰寫分割，可用**istringstream**: 
    * 介紹:[https://blog.csdn.net/longzaitianya1989/article/details/52909786]
    * 簡單用法: [https://blog.csdn.net/Cyril_KI/article/details/119729977]

``` cpp=
#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        unordered_map<char, string> dic;
        istringstream split(s);
        vector<string> token;
        string curWord;
        while( split>>curWord){
            token.push_back(curWord);
        }
        if (pattern.size()!=token.size()) return false;
        for (int i=0; i<pattern.size(); i++){
            if (dic.find(pattern[i])!=dic.end()){
                if (dic[pattern[i]]!=token[i])
                    return false;
            }
            else{
                //item.first: key; item.second: value
                for (auto& item: dic){
                    if (dic[item.first]==token[i])
                        return false;
                }
                dic[pattern[i]]=token[i];
            }
        }
        return true;
    }
};
```