词语模式_哈希表

思考与分析

匹配:字符串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;
    }
}