leetcode-290-Word Pattern

chenjx85

发布于 2018-05-21 18:44:02

5880

发布于 2018-05-21 18:44:02

题目描述：

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.

要完成的函数：

bool wordPattern(string pattern, string str)

说明：

1、这道题目是之前char-char的升级版，现在是char-string。要求不变，仍然是不能两个相同的字母对应一个string，不能两个相同的string对应一个字母。仿照之前思路，很容易构造出代码。

2、这道题目还要注意有可能pattern里面的字母个数和string里面的单词个数不匹配，边界条件处理一下就好了。

代码如下：

    bool wordPattern(string pattern, string str) 
    {
        map<char,string>m1;
        map<string,char>m2;
        int j=0;
        string str1="";//存储str中切分出来的单词
        for(int i=0;i<pattern.size();i++)
        {
            str1="";
            if(j>str.size())//如果pattern的字母多于str中的单词
                return false;

            while(str[j]!=' '&&str[j]!='\0')//碰到空格和str末尾的'\0'就停下
            {
                str1+=str[j];
                j++;
            }
            j++;  //j设置为下一个单词首字母的index
 
            if(m1[pattern[i]]=="")
        　　　　m1[pattern[i]]=str1;
            else
            {
                if(m1[pattern[i]]!=str1)
                   return false;
            }

            if(!m2[str1])
        　　　　m2[str1]=pattern[i];
            else
            {
                if(m2[str1]!=pattern[i])
                    return false;
            }
        }

        if(j<str.size())//如果str中单词多于pattern中字母
            return false;
        return true;
    }

m1是用来防止“aa”和“dog cat”这种一个字母对应两个不同单词的情况。m2则是用来防止“ab”和“dog dog”这种两个字母对应同一个单词的情况。

上述代码实测2ms，beats 100% of cpp submissions。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018-04-15 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度