首页 > 其他 > 详细

(LeetCode)Word Pattern --- 模式匹配

时间:2016-08-16 10:39:56      阅读:195      评论:0      收藏:0      [点我收藏+]

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:

  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:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

Credits:
Special thanks to @minglotus6 for adding this problem and creating all test cases.

Subscribe to see which companies asked this question


解题分析:

题目的意思是给出一个字符串 str, 再给出一个模式 pattern,然后要求就是判断给出的字符串是否和给出的模式相匹配,

匹配的话就返回True, 否则返回False.


思路一:

     利用hash思想将pattern做索引,str为值存储,与str为索引,pattern为值进行匹配。

# -*- coding:utf-8 -*-
__author__ = 'jiuzhang'
class Solution(object):
    def wordPattern(self, pattern, str):
        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



思路二:

利用位置进行匹配。

使用 index 以及,map,find 函数。

# -*- coding:utf-8 -*-
__author__ = 'jiuzhang'
class Solution(object):
    def wordPattern(self, pattern, str):
        s = pattern
        t = str.split()
        return map(s.find, s) == map(t.index, t)







(LeetCode)Word Pattern --- 模式匹配

原文:http://blog.csdn.net/u012965373/article/details/52217651

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!