Leetcode 290. Word Pattern

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Examples:

  1. pattern = "abba", str = "dog cat cat dog" should return true.
  2. pattern = "abba", str = "dog cat cat fish" should return false.
  3. pattern = "aaaa", str = "dog cat cat dog" should return false.
  4. pattern = "abba", str = "dog dog dog dog" should return false.

Notes: You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

判断字符串是否是模式串的形式。

对字符串进行分词,用map保存和模式串字符的对应关系

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        str += " ";
        int j = 0;
        unordered_map<string, string> mp;
        for(int i = 0; i < str.size(); i++)
        {
            int pos = str.find(" ", i);
            string tmp = str.substr(i, pos - i);
            i = pos;
            if(j == pattern.size()) return false;
            string key(pattern[j] + "\0");
            if(mp.find(key) == mp.end())
            {
                if(mp.find(tmp) == mp.end()) 
                {
                    mp[tmp] = key;
                    mp[key] = tmp;
                }
                else return false;
            }
            else if(mp[key] != tmp) return false;
            j++;
        }
        if(j != pattern.size()) return false;
        return true;
    }
};

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏对角另一面

lodash源码分析之compact中的遍历

本文为读 lodash 源码的第三篇,后续文章会更新到这个仓库中,欢迎 star:pocket-lodash

22560
来自专栏程序员互动联盟

【C++练手】C++实现单链表

前几天找实习的时候,一个面试官给我留了一个题,做一个链表demo,要求实现创建、插入、删除等操作。 链表是一种常见的数据结构,它是一种物理存储单元上非连续、非顺...

35170
来自专栏计算机视觉与深度学习基础

Leetcode 290. Word Pattern

Given a pattern and a string str, find if str follows the same pattern. Here ...

39390
来自专栏云瓣

前端中常见数据结构小结

数据结构在开发中是一种编程思想的提炼,无关于用何种语言开发或者是哪种端开发。下列将笔者涉猎到的与前端相关的数据结构案例作如下总结:

8210
来自专栏阿杜的世界

Java并发-CopyOnWriteArrayList前言CopyOnWriteArrayList API例子1:插入(删除)数据的同时进行遍历例子2:不支持一边遍历一边删除结论参考资料

今天我们一起学习下java.util.concurrent并发包里的CopyOnWriteArrayList工具类。当有多个线程可能同时遍历、修改某个公共数组时...

16030
来自专栏codingforever

经典算法巡礼(七) -- 排序之堆排序

很多时候,我们需要处理有序的元素,但不一定要求它们全部有序,或是不一定要一次就将它们排序。比如你可能启动了若干个定时器,那么下一次处理定时器事件只需要考虑距离现...

8120
来自专栏小灰灰

Java容器篇小结之List自问自答

I. List篇 0. 什么是List 看到这个有点懵逼,一时还真不知道怎么解释,能让完全没有接触过的人都能听懂 列表,什么是列表呢? 好比你到了一个村里,看...

22580
来自专栏计算机视觉与深度学习基础

Leetcode 179 Largest Number

Given a list of non negative integers, arrange them such that they form the lar...

271100
来自专栏王磊的博客

Java核心(四)面试必备—你不知道的数据集合

导读:Map竟然不属于Java集合框架的子集?队列也和List一样属于集合的三大子集之一?更有队列的正确使用姿势,一起来看吧!

11220
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——Set汇总

324120

扫码关注云+社区

领取腾讯云代金券