词语模式_哈希表

已知字符串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 条评论
登录 后参与评论

相关文章

来自专栏开源优测

[快学Python3]if条件控制

if语句 先看下Python中一般的条件控制语句的形式是怎么样的,如下所示: if 条件: # 代码块 elif 条件: ...

20640
来自专栏Vamei实验室

Python基础03 序列

sequence 序列 sequence(序列)是一组有顺序的元素的集合 (严格的说,是对象的集合,但鉴于我们还没有引入“对象”概念,暂时说元素) 序列可以包含...

20450
来自专栏数据结构与算法

03:八进制小数

03:八进制小数 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 八进制有限小数均可以用十进制有限小数精确地表示。比如,八...

37370
来自专栏流媒体

C语言数组

20330
来自专栏python3

python3--函数进阶

TypeError: func() missing 4 required keyword-only arguments: 'a', 'b', 'c', and ...

9810
来自专栏尾尾部落

普林斯顿大学算法公开课笔记——选择排序 普林斯顿大学算法公开课笔记——选择排序

简单选择排序的特点是交换移动次数很少(至多n-1次),其时间复杂度为 O(n²) (时间主要花在比较上,总的比较次数为N=(n-1)+(n-2)+…+1=n*(...

10430
来自专栏小樱的经验随笔

strncmp函数——比较特定长度的字符串

strncmp函数用于比较特定长度的字符串。 头文件:string.h。 语法  int strncmp(const char *string1, const ...

35890
来自专栏desperate633

LintCode 两个字符串是变位词题目分析代码

写出一个函数 anagram(s, t) 判断两个字符串是否可以通过改变字母的顺序变成一样的字符串。

10320
来自专栏Laoqi's Linux运维专列

函数的变量+返回值

12340
来自专栏我爱编程

Day7函数式编程3/3

装饰器 由于函数也是一个对象,而且函数对象可以被赋值给变量,所以,通过变量也能调用该函数。 >>> def now(): ... print('2018...

38070

扫码关注云+社区

领取腾讯云代金券