专栏首页书山有路勤为径词语模式_哈希表

词语模式_哈希表

已知字符串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;
    }
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Convolutional Neural Networks

    计算机视觉(Computer Vision)包含很多不同类别的问题,如图片分类、目标检测、图片风格迁移等等。

    小飞侠xp
  • client library&roscpp

    ROS为机器人开发者提供了不同语言的编程接口,比如C++接口叫做roscpp,python接口叫做rospy,Java接口叫做rosjava。尽管语言不通,但这...

    小飞侠xp
  • Service in roscpp

    Service是一种请求-反馈的通信机制。请求的一方通常被称为客户端,提供服务的一方叫做服务器端。Service机制相比于Topic的不同之处在于:

    小飞侠xp
  • LeetCode 图解 | 290 . 单词规律

    题目来源于 LeetCode 上第 290 号问题:单词规律。题目难度为 Easy,目前通过率为 42.4% 。

    五分钟学算法
  • 迄今为止最硬核的「Java8时间系统」设计原理与使用方法

    Java平台时间系统的设计方案 几乎任何事物都会有“起点”这样的概念,比如人生的起点就是我们出生的那一刻。 Java平台时间系统的起点就是世界时间(UTC)...

    Java团长
  • 夯实Python基础(6)

    os.rmdir() 删除空目录(删除非空目录, 使用shutil.rmtree())

    高一峰
  • 【解读】遗传基因程序二元机器代码自动归纳合成算法

    可能这个算法出来已经一段时间了,今天在一个策略网站上偶然发现,觉得很有意思,因此,查阅了一些资料进行学习。 遗传基因程序二元机器代码自动归纳合成算法(Autom...

    量化投资与机器学习微信公众号
  • 1009. 说反话 (20)

    输入格式:测试输入包含一个测试用例,在一行内给出总长度不超过80的字符串。字符串由若干单词和若干空格组成,其中单词是由英文字母(大小写有区分)组成的字符串,单词...

    AI那点小事
  • 基础知识 | 每日一练(162)

    小林:这非常困难,即使你可以找出一个可行的方法, 你可能会考虑通过环境变量或别的方法使程序的辅助 (函数库) 目录可配置。如果程序会被数个人使用, 例如在多用户...

    C语言入门到精通
  • 微信小程序云端解决方案探索之路 - GITC 主题演讲

    在刚结束的全球互联网技术大会(GITC)里面,我在前端专场给大家分享了「微信小程序云端解决方案探索之路」,介绍到了我们之前对小程序云端解决方案的探索过程。

    小芭乐

扫码关注云+社区

领取腾讯云代金券