题目描述：

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/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

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