290. 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.

题解：

输入两个字符串，一个是字符组成的字符串，一个用空格分开的字符串组成的字符串；判断这两个字符串的结构组成是否匹配；

分析：

我们依照空格将 str 中的各单词分开；对每个单词，判断该位置对应的字符是否存在：
例如：
pattern = "abba", str = "dog cat cat dog" ，首先判断hash_map["dog"]是否存在：

1. hash_map["dog"]存在：判断hash_map["dog"] 是否等于‘a’；不相等false；相等继续判断；
2. hash_map["dog"]不存在：判断‘a’是否使用过，使用过的话false；未使用过的话，让hash_map["dog"] = ‘a’；继续判断；这里我们用used记录字符的使用情况；

重复上述过程，直到所有的单词都判断完成，说明全部配对成功，返回true；
考虑特殊情况，当pattern中的字符数和str中的单词数目不等时，返回false；

My Solution(C/C++)

#include <cstdio>
#include <iostream>
#include <string>
#include <map>

using namespace std;

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        map<string, char> hash_map;
        str += ' ';
        string word;
        int index = 0;
        int used[128] = {0};
        for (int i = 0; i < str.length(); i++) {
            if (str[i] != ' ') {
                word += str[i];
            }
            else {
                if (index < pattern.length()) {
                    if (hash_map.find(word) != hash_map.end()) {  //hash_map 中字符串已经存在对应的字符；
                        if (hash_map[word] != pattern[index]) {
                            return false;
                        }
                    }
                    else {
                        if (used[pattern[index]] == 0) {
                            hash_map.insert(map<string, char>::value_type(word, pattern[index]));
                            used[pattern[index]] = 1;
                        }
                        else {
                            return false;
                        }
                    }
                    word = "";
                    index += 1;
                }
                else {
                    return false;
                }
            }
        }
        if (index != pattern.length()) {
            return false;
        }
        return true;
    }
};

int main() {
    Solution s;
    cout << s.wordPattern("abab", "LdpcII cool LdpcII cool") << endl;
    cout << s.wordPattern("aaaa", "LdpcII is not cool");
    return 0;
}

结果

1
0

My Solution:

class Solution:
    def wordPattern(self, pattern, str):
        """
        :type pattern: str
        :type str: str
        :rtype: bool
        """
        char_map = [0 for i in range(128)]
        used, mark = [], 0
        s = str.split()
        if len(pattern) != len(s):
            return False
        for i in range(len(pattern)):
            for p in used:
                if p == pattern[i]:
                    if char_map[ord(p)] != s[i]:    # pattern = "aaaa", str = "dog cat cat dog"
                        return False
                    else:
                        mark = 1
                else:
                    if char_map[ord(p)] == s[i]:    # pattern = "abba", str = "dog dog dog dog"
                        return False
            if mark == 0:
        #         # if char_map[ord(pattern[i])] == 0:    
                char_map[ord(pattern[i])] = s[i]
                used.append(pattern[i])      
        return True
        

Reference:

class Solution(object):
    def wordPattern(self, pattern, str):
        """
        :type pattern: str
        :type str: str
        :rtype: bool
        """
        x = str.split(' ')
        lsp = len(set(pattern))
        lsx = len(set(x))
        return len(x)==len(pattern) and lsx==lsp and lsp== len(set(zip(pattern, x)))