leetcode Word Pattern

leetcode Word Pattern

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

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:

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

题目地址： leetcode Word Pattern

题意：

给定一个模式串和一个字符串，判断模式串是否符合字符串的描述。

如，

模式串为abba  ,字符串为dog cat cat dog 返回true

模式串为abba  ,字符串为dog cat cat fish 返回false

• 模式串和字符串只有小写字母，开头和结尾都没有多余的字符
• 在字符串中所有单词被一个空格划分
• 模式串必须匹配字符串至少长度为1的单词

 

思路：

先把字符串根据空格划分。

接着我采用双字典的方式，分别记录最后出现的下标，详见代码吧，很好理解的

class Solution(object):
    def wordPattern(self, pattern, str):
        """
        :type pattern: str
        :type str: str
        :rtype: bool
        """
        str = str.split()
        str_index , pattern_index = {},{}
        n = len(pattern)
        if n != len(str):
            return False
        for i in xrange(n):
            if pattern[i] in pattern_index:
                if str[pattern_index[pattern[i]]] != str[i]:
                    return False
            else:
                if str[i] in str_index:
                    return False
                str_index[str[i]] = i
                pattern_index[pattern[i]] = i

        return True