[LeetCode]Word Pattern

题目描述:

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

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:

Both pattern and str contains only lowercase alphabetical letters.
Both pattern and str do not have leading or trailing spaces.
Each word in str is separated by a single space.
Each letter in pattern must map to a word with length that is at least 1.

题目大意:

给定一个模式pattern和一个字符串str,判断str是否满足相同的pattern。

测试用例如题目描述。

注意:

pattern和str都只包含小写字母。
pattern和str不包含前导或者后缀空格。
str中的每一个单词之间都由一个空格分开。
pattern中的每一个字母都对应一个长度至少为1的单词。

解题思路:

使用字典dict分别记录pattern到word的映射以及word到pattern的映射

这道题和题目Isomorphic Strings十分类似

Python代码:

class Solution(object):
    def wordPattern(self, pattern, str):
        """
        :type pattern: str
        :type str: str
        :rtype: bool
        """
        words = str.split()
        if len(pattern) != len(words):
            return False
        ptnDict, wordDict = {}, {}
        for ptn, word in zip(pattern, words):
            if ptn not in ptnDict:
                ptnDict[ptn] = word
            if word not in wordDict:
                wordDict[word] = ptn
            if wordDict[word] != ptn or ptnDict[ptn] != word:
                return False
        return True

另附两段十分简短的Python代码,摘自LeetCode Discuss

链接地址:https://leetcode.com/discuss/62333/short-in-python

Python代码(1):

def wordPattern(self, pattern, str):
    s = pattern
    t = str.split()
    return map(s.find, s) == map(t.index, t)

Python代码(2):

def wordPattern(self, pattern, str):
    s = pattern
    t = str.split()
    return len(set(zip(s, t))) == len(set(s)) == len(set(t)) and len(s) == len(t)

以及一段简短的Java代码

摘自:https://leetcode.com/discuss/62374/9-lines-simple-java

使用了HashMap对象put方法返回值的特性,比较pattern中的字母与str中的单词下标对应关系是否一致

Java代码:

public boolean wordPattern(String pattern, String str) {
    String[] words = str.split(" ");
    if (words.length != pattern.length())
        return false;
    Map index = new HashMap();
    for (int i=0; i<words.length; ++i)
        if (!Objects.equals(index.put(pattern.charAt(i), i),
                            index.put(words[i], i)))
            return false;
    return true;
}

 

本文链接:http://bookshadow.com/weblog/2015/10/05/leetcode-word-pattern/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

评论
  1. JamesFJX JamesFJX 发布于 2016年5月29日 13:50 #

    Python代码(2)已经无法通过了,因为多了‘aaa’和‘aa aa aa aa’的case,要考察两者长度是否一样,所以要把return改成

    return len(s)==len(t) and len(set(zip(s,t)))==len(set(s))==len(set(t))

    才能通过

  2. 在线疯狂 在线疯狂 发布于 2016年5月31日 15:07 #

    感谢提醒!已经对代码做了更正! :)

张贴您的评论