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

# 290. Word Pattern

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

## 題目:

## 解題想法:
* 此題為判斷合法映射
* 每個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:

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]

#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;
    }
};