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操作系...

    行 者
  • 接口默认方法和 Lambda 表达式

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

    happyJared
  • 全连接神经网络(下)

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

    公众号guangcity
  • MySQL使用on duplicate key update时导致主键不连续自增

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

    JouyPub
  • 老生常谈!数据库如何存储时间?你真的知道吗?

    我们平时开发中不可避免的就是要存储时间,比如我们要记录操作表中这条记录的时间、记录转账的交易时间、记录出发时间等等。你会发现这个时间这个东西与我们开发的联系还是...

    Guide哥
  • 【数据结构与算法】一起搞定面试中的二叉树(一)

    最近总结了一些数据结构和算法相关的题目,这是二叉树相关面试题的总结,是用java实现的,由于篇幅有限,因此分为两部分,这是第一部分总结。先上二叉树的数据结构:

    用户1634449

扫码关注云+社区

领取腾讯云代金券