专栏首页算法其实很好玩Day9-字符串-字符模式匹配

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

一 唠唠嗑

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

二 上题!

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的使用了解了

//
// 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,不匹配

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

//
// 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原理

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

本文分享自微信公众号 - 算法其实很好玩(AlgorithmBUPTrenyi),作者:BUPTrenyi

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-06-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 基础知识-操作系统-虚拟内存

    虚拟内存是相对于物理内存的一种说法。那么什么是物理内存呢?顾名思义,插在主板上的内存条是多大,内存就是多大。

    BUPTrenyi
  • Day12-字符串-重复的DNA序列

    Q:将DNA序列看作是只包含【'A', 'C', 'G', 'T'】4个字符的字符串。现有一个这样的字符串,找到所有长度为10且出现次数超过1的子串。

    BUPTrenyi
  • Day16-递归&回溯-有重复数组的子集

    其实今天这道题本应该在昨天的,第二篇文章中的,奈何需求多而紧,着实没时间写第二篇文章了,你们可不要以为我是划水啊

    BUPTrenyi
  • OpenCV 几何变换-图像镜像

    图像镜像是图像基本的几何变换之一,实现起来也很简单,先贴上源码: #include <opencv/highgui.h> #include <time.h>...

    chaibubble
  • 「国王-男人+女人=皇后」背后的词类比原理究竟为何?| ACL 2019

    AI 科技评论按:在近些年的自然语言处理研究中,「词类比」是一个十分有趣的现象,最经典的例子莫过于「国王-男人+女人=皇后」。然而,如何将神经网路的黑盒拆开从而...

    AI科技评论
  • Unity3D网络通讯(四)--Socket通讯之Tcp通讯

    UnityWebRequest通过Restful的通讯我们已经实现了,《笔记|Unity异步处理与UI Text显示的问题》章中在做Tcp通讯时因为用到了异步处...

    Vaccae
  • JavaScript Source Map 详解

    上周,jQuery 1.9发布。 ? 这是2.0版之前的最后一个新版本,有很多新功能,其中一个就是支持Source Map。 访问 http://ajax.go...

    ruanyf
  • Linux内存初始化(上)

    有了armv8架构访问内存的理解,我们来看下linux在内存这块的初始化就更容易理解了。

    刘盼
  • (16/24) webpack打包后的调试方法

    在程序开发中,调试程序是最频繁的,那使用了webpack后,所有的代码都打包到了一起,这给调试带来了困难,但是webpack在设计时就已经考虑好了这点,它支持生...

    wfaceboss
  • 你是个成熟的C位检测器了,应该可以自动找C位了

    C位是近年网络上一个比较热门的词,最早来源于DOTA等游戏领域,是核心位置(Carry位)的简称,代表的是能够在游戏前中期打钱发育并在游戏后期带领队伍力挽狂澜的...

    AI科技大本营

扫码关注云+社区

领取腾讯云代金券