前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Day9-字符串-字符模式匹配

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

作者头像
BUPTrenyi
发布2019-07-15 16:53:46
6100
发布2019-07-15 16:53:46
举报
文章被收录于专栏:算法其实很好玩

一 唠唠嗑

今天有点晚,直接上题了,一毛钱的都不跟你们唠

二 上题!

Q:已知字符串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"不匹配.

三 想想?

冷静分析:

1.当切分出一个单词时,若该单词已出现过,那么这个单词对应的pattern字符,必须也是之前出现时对应的pattern字符

2.当切分出一个单词时,若该单词没有出现过,则与之对应的pattern字符也不能出现过

3.单词的个数必须与pattern中字符的数量相同

那么问题来了,我们怎么将一个单词和一个字符绑定在一起呢?

这里引入新的概念,哈希map

如果用一句话解释,它就是个key-value的数据结构,保存的是key到value的映射

在c++标准STL中也支持了这种数据结构,只需#include<map>即可使用

举个栗子,大家就对哈希map的使用了解了

代码语言:javascript
复制
//
// 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;
}

运行结果

怎么样,是不是对hash map的用法瞬间通透了

在这还要十分建议大家底下自行了解一下hash map原理,十分有用,你懂得

好了,知道怎么用hash map之后,我们可以这样处理逻辑:

1.建立单词到单个字符的哈希映射,使用数组used[128]来标志,当前的单个字符是否已被使用

2.遍历单词字符串str,按照空格切分单词,同时移动pattern下标,判断:

如果该单词从未出现在哈希表中:

如果当前的pattern单个字符已被使用,返回false,不匹配;

如果当前pattern字符没被使用,那么:

建立该单词到单个字符的映射,同时标记单个字符已被使用;

如果该单词出现在了哈希表中:

检查该单词应该匹配的字符,是否与当前pattern字符相同,如果相同,则匹配,如果不相同,则返回false

如果单词个数与pattern字符数量不一致:

返回false,不匹配

四 完整代码及十分详细的注释

代码语言:javascript
复制
//
// 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;
}

测试一下:

不匹配的

匹配的

五 总结

还是一定要了解hash map原理

好了,有点晚了,实现一下,然后大家晚安

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-06-13,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 算法其实很好玩 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档