词语模式_哈希表

已知字符串pattern与字符串str，确认str是否与pattern匹配。str与pattern匹配代表字符 串str中的单词与pattern中的字符一一对应。(其中pattern中只包含小写字符，str中的单词只包含小写字符，使用空格分隔。) 例如， pattern = “abba”, str = “dog cat cat dog” 匹配. pattern = “abba”, str = “dog cat cat fish” 不匹配. pattern = "aaaa", str = "dog cat cat dog"不匹配. pattern = "abba", str = "dog dog dog dog"不匹配. LeetCode 290. Word Pattern

思考与分析

匹配:字符串str中的单词与pattern中的字符一一对应。 如: 1)假设pattern = “abba”， str = “dog cat cat ” ;则一定代表dog。 2)假设pattern = “abb?”， str = “dog cat cat dog” ;则?一定代表a。 3)假设pattern = “abb?”， str = “dog cat cat fish” ;则?一定不是a或b。 4)假设pattern = “abba”，str = “”;代表了4个单词，且第1、4单词相同;2、3单词相同，并且 1、2两个单词不同。 5)假设pattern = “”，str = “dog cat cat dog”;代表了4个字符，且1、4字符相同;2、3字符相 同，并且1、2两个字符不同。

分析结论: 以单词为单位进行拆解与判断: 1.当拆解出一个单词时，若该单词已出现，则当前单词对应的pattern字符必为该单词曾经对 应的pattern字符。 2.当拆解出一个单词时，若该单词未曾出现，则当前单词对应的pattern字符也必须未曾出现 。 3.单词的个数与pattern字符串中的字符数量相同。

算法设计

pattern = “abb?”， str = “dog cat cat *”; dog -> a;cat->b 1.设置单词(字符串)到pattern字符的映射(哈希);使用数组used[128]记录pattern字符是否使用。 2.遍历str，按照空格拆分单词，同时对应的向前移动指向pattern字符的指针，每拆分出一个 单词，判断: 如果该单词从未出现在哈希表中: 如果当前的pattern字符已被使用，则返回false; 将单词与当前指向的pattern字符做映射; 标记当前指向的pattern字符已使用。 否则 如果当前单词在哈希表中的映射字符不是当前指向的 pattern字符，则返回false。 3.若单词个数与pattern字符个数不匹配，返回false。

class Solution{
public:
    bool wordPattern(std::string pattern, std::string str){
    std::map(std::string,char) word_map;//单词到pattern字符的映射
    char used[128] = {0};//已被映射的pattern字符
    std::string word;//临时保存拆分出来的单词
    int pos = 0; //当前指向的pattern字符
    str.push_back(' ');//str尾部push一个空格，使得遇到空格拆分单词
    for(int i =0; i < str.length(); i++){
        if(str[i] == '  '){//遇到空格，即拆分一个新单词
            if(pos == pattern.length()){
                return false;
            }
//若单词未出现在哈希映射中
            if(word_map.find(word) == word_map.end()){
                if(used[pattern[pos]]){//如果当前pattern字符已使用
                    return false; 
                }
                word_map[word] = pattern[pos];
                used[pattern[pos]] = 1;   
            }
            else{
                if(word_map[word] != pattern[pos]){//若当前word已建立映射无法与当前pattern对应
                    return false;
                }
            }
            word = " ";//完成一个单词的插入和查询后，清空word
            pos++;  
        }
        else{
            word += str[i];
        }
    }
    if(pos != pattern.length()){
        return false;
    }
    return true;
    }
}