Day9-字符串-字符模式匹配

//
// Created by renyi on 2019-06-13.
//
#include <iostream>
#include <map>
#include <string>
using namespace std;

int main(){
    map<string, int> hash_map;//初始化一个字符串string到整型int的映射，即哈希map
    string string1 = "abc";
    string string2 = "aaa";
    string string3 = "wwwwwww";
    //建立了三个字符串到整型的映射
    hash_map[string1] = 1;
    hash_map[string2] = 2;
    hash_map[string3] = 3;

    if (hash_map.find(string1) != hash_map.end()){//如果在哈希map中找到了string1
        printf("%s is in hash map, and it's value is:%d\n", string1.c_str(), hash_map[string1]);
    }

    map<string, int> ::iterator it;//初始化一个迭代器指针it，指向一个从string到int的映射
    for (it = hash_map.begin(); it != hash_map.end(); it++) {//it指向了hash_map
        printf("hash_map[%s] = %d\n", it->first.c_str(), it->second);//it->first就是当前的映射的第一个元素，就是字符串string，it->second同理
    }
    return 0;
}

//
// Created by renyi on 2019-06-13.
//
#include <iostream>
#include <string>
#include <map>
using namespace std;

bool wordPattern(string pattern, string str){
    map<string, char> word_map;//初始化单词到pattern字符的映射，即哈希map
    char used[128] = {0};//初始化一个字符数组，即字符哈希，保存已被映射过的pattern字符
    string word;//临时保存拆分出来的单词
    int position = 0;//当前指向的pattern字符
    str.push_back(' ');//保存单词的str，尾部push一个空格，使遇到空格，切分最后一个单词

    for (int i = 0; i < str.length(); i++) {
        if (str[i] == ' '){//遇到了空格，即切分出了一个单词
            if (position == pattern.length()){//若此时position位置为pattern长度（注意pattern下标从0开始），即超出了pattern长度，pattern已无字符对应
                return false;
            }

            if (word_map.find(word) == word_map.end()){//在哈希map中找不到word时，find函数返回的迭代器指针，与end函数返回的迭代器指针相同，即，当该单词从未出现在哈希map中
                if (used[pattern[position]]){//若当前pattern字符已使用,返回错误.比如“dog dog fish”和“aaa”
                    return false;
                }
                word_map[word] = pattern[position];//建立单词到单个字符的映射
                used[pattern[position]] = 1;//把当前单个字符的used数组
            }
            else {//若find函数返回的迭代器指针不等于end函数返回的迭代器指针，即哈希map中已找到了该单词，即当前单词已与单个字符建立映射
                if (word_map[word] != pattern[position]){
                    return false;//如果当前已经与单词建立映射的单个字符，并不等于pattern中的字符，即比如“dog cat cat”与“abc”
                }
            }
            word = "";//将临时变量pattern置空
            position++;//pattern的下标，即position向后移

        } else{//没遇到空格，就把当前字符累加到word中，遇到空格时，word就是一个完整的单词了
            word += str[i];
        }
    }
    if (position != pattern.length()){
        return false;//当单词str遍历结束，position还没到pattern尾，说明pattern更长，无法满足匹配
    }
    return true;//前面的false都没走到，即正常匹配，返回true
}

int main(){
    string pattern = "abba";
    string str = "dog cat cat fish";
    if (wordPattern(pattern, str)){
        printf("字符串:%s,与pattern:%s 正常匹配\n", str.c_str(), pattern.c_str());
    } else{
        printf("字符串:%s,与pattern:%s 不匹配\n", str.c_str(), pattern.c_str());
    }
    return 0;
}