【一天一道LeetCode】#290. Word Pattern

一天一道LeetCode

本系列文章已全部上传至我的github,地址:ZeeCoder‘s Github
欢迎大家关注我的新浪微博,我的新浪微博
欢迎转载,转载请注明出处

(一)题目

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:

  • pattern = “abba”, str = “dog cat cat dog” should return true.
  • pattern = “abba”, str = “dog cat cat fish” should return false.
  • pattern = “aaaa”, str = “dog cat cat dog” should return false.
  • 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.

(二)解题

题目大意:字符串模式匹配。给定模板字符串pattern和待匹配字符串str,判断str是否与pattern模式匹配
解题思路:这是一道典型应用hash表求解的题。
利用两个辅助的hash表实现字符串的双向匹配。例如a->dog,dog->a
不允许出现模式中两个不同的字符对应str中同一个单词。
具体思路见代码:

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        int lenp=pattern.length();
        int lens=str.length();
        int i = 0;
        int j = 0;
        unordered_map<string,char> hash;//两个hash表,双向匹配
        unordered_map<char,string> hash2;
        while(i<lenp&&j<lens){
            string temp;
            while(j<lens&&str[j]!=' '){//找出str中以空格分隔的字符串
                temp+=str[j++];
            }
            auto iter = hash.find(temp);
            auto iter2 = hash2.find(pattern[i]);
            if(iter==hash.end()&&iter2==hash2.end()){//如果都不存在
                hash[temp] = pattern[i];
                hash2[pattern[i]] = temp;//记录双向匹配关系
            }
            else{
                if(hash[temp]==pattern[i]&&hash2[pattern[i]]==temp) {}
                else return false;//匹配不上
            }
            i++;j++;
        }
        return i>=lenp?j>=lens?true:false:false;//最后需要判断两个字符串是否匹配完
    }
};

推荐文章

Visual C++ 2010代码完成

Visual C++ 2010代码完成

推荐文章

如何更新我的实体框架

如何更新我的实体框架

推荐文章

Android traceview备选方案

Android traceview备选方案

推荐文章

Oracle SQL查询或集群地理数据的函数

Oracle SQL查询或集群地理数据的函数

推荐文章

带有静态库项目和应用程序项目的Xcode4工作区

带有静态库项目和应用程序项目的Xcode4工作区

推荐文章

在FitSharp中使用符号

在FitSharp中使用符号

推荐文章

MVC 3 Ajax.BeginForm的有效XHTML失败了?

MVC 3 Ajax.BeginForm的有效XHTML失败了?

推荐文章

智能手机与移动网络应用相比有什么好处?

智能手机与移动网络应用相比有什么好处?

推荐文章

Rails,gemfile中的许多gems会减慢站点的速度吗?

Rails,gemfile中的许多gems会减慢站点的速度吗?

推荐文章

在DEV-C++中编译Windows程序给出错误

在DEV-C++中编译Windows程序给出错误

推荐文章

iPhone-backbarbuttonem为零,触摸时不亮显

iPhone-backbarbuttonem为零,触摸时不亮显

推荐文章

PHP include当“根正斜杠”位于包含路径之前时,例如:“/folder/file.PHP”

PHP include当“根正斜杠”位于包含路径之前时,例如:“/folder/file.PHP”

推荐文章

在Visual studio中关闭WCF服务主机

在Visual studio中关闭WCF服务主机

推荐文章

如何在不修改提供的Rails.js的情况下重写Rails 3不引人注目的javascript函数?

如何在不修改提供的Rails.js的情况下重写Rails 3不引人注目的javascript函数?

推荐文章

何时使用get;set;in c#

何时使用get;set;in c#

推荐文章

Symfony2路由-路由子域

Symfony2路由-路由子域