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 条评论
登录 后参与评论

相关文章

  • Leetcode 290. Word Pattern

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

    triplebee
  • 计算机视觉与图像处理学习笔记(二)win32+mingw+opencv搭建

    本来是想接着第二章学习的,但是感觉理论性有点强,了解基本概念后还是从Opencv来,遇到问题再切换。 关于opencv的下载与配置参考: http://open...

    triplebee
  • Leetcode 13 Roman to Integer

    Given a roman numeral, convert it to an integer. Input is guaranteed to be wit...

    triplebee
  • Leetcode 290. Word Pattern

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

    triplebee
  • Centos7部署HAproxy实现Nginx群集

    Haproxy是一个使用C语言编写的自由及开放代码软件,其提供高可用性、负载均衡,以及基于TCP和HTTP的应用程序代理,可以运行于大部分主流的Linux操作系...

    行 者
  • 全连接神经网络(下)

    0.说在前面1.Batch Normalization1.1 什么是BN?1.2 前向传播1.3 反向传播2.Dropout2.1 什么是Dropout?2.2...

    公众号guangcity
  • 接口默认方法和 Lambda 表达式

    Java8 使开发者能够通过使用 default 关键字向接口添加非抽象方法实现,也称为虚拟扩展方法。

    happyJared
  • MySQL使用on duplicate key update时导致主键不连续自增

    在做数据统计的时候,我们经常会用到mysql的on duplicate key update语法来自动更新数据,比如

    JouyPub
  • 快速了解Electron:新一代基于Web的跨平台桌面技术

    现在开发IM应用动不动就要求多端——即Android端、iOS端、PC端、Web端等,Android端和iOS端作为两种不同的移动端技术,单独开发和维护还能理解...

    JackJiang
  • SCI规范作图(Matlab)+简洁干货+源代码+免费

    折线走势图是所有文章必不可少的数据分析直观展现方式,本文以上图为例,以小见大来说明如何用Matlab画出SCI投稿专用单栏图片:线形、标记点、线宽、坐标...

    梁佐佐

扫码关注云+社区

领取腾讯云代金券