LeetCode 290. Word Pattern

简介: 给定一种 pattern(模式) 和一个字符串 str ,判断 str 是否遵循相同的模式。这里的遵循指完全匹配,例如, pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应模式。

v2-745a69ae2c429670f7a50c66b7080792_1440w.jpg

Description



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.


Example 1:


Input: pattern = "abba", str = "dog cat cat dog"
Output: true


Example 2:


Input:pattern = "abba", str = "dog cat cat fish"
Output: false


Example 3:


Input: pattern = "aaaa", str = "dog cat cat dog"
Output: false


Example 4:


Input: pattern = "abba", str = "dog dog dog dog"
Output: false


Notes:


You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.


描述



给定一种 pattern(模式) 和一个字符串 str ,判断 str 是否遵循相同的模式。

这里的遵循指完全匹配,例如, pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应模式。


示例1:


输入: pattern = "abba", str = "dog cat cat dog"
输出: true


示例 2:


输入:pattern = "abba", str = "dog cat cat fish"
输出: false


示例 3:


输入: pattern = "aaaa", str = "dog cat cat dog"
输出: false


示例 4:


输入: pattern = "abba", str = "dog dog dog dog"
输出: false


说明:

你可以假设 pattern 只包含小写字母, str 包含了由单个空格分隔的小写字母。


思路



  • 模式串中的每个字母要和给定的单词建立一一对应的关系.
  • 我们用一个字典建立这种关系;1. 如果当前模式串中的字母不在字典中,我们建立字母和单词的对应关系;2. 如果当前模式串中的字母在字典中:如果当前的单词出现在字典的值中,说明当前单词已经和别的字母建立了对应关系,返回Fasle;如果当前单词没有在字典的值中,我们建立模式串字母和单词的对应关系;3.如果当前模式串字母在字典中,如果字典中模式串对应的值与当前单词不等,我们返回False;4. 如果上面的条件头能够通过,我们最后返回True.


# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-02-08 11:19:39
# @Last Modified by:   何睿
# @Last Modified time: 2019-02-09 09:43:27
class Solution:
    def wordPattern(self, pattern: 'str', str: 'str') -> 'bool':
        #  字典,记录对应关系
        match = {}
        # 将给定的单词用空格区分
        word = str.split(" ")
        # 如果长度不相等,直接返回False
        if len(pattern) != len(word): return False
        for i in range(len(pattern)):
            # 如果模式串pattern[i]不在字典中(键)
            if pattern[i] not in match:
                # 如果此时的单词在字典的值中,说明已经有模式串的字符与当前单词匹配,返回False
                if word[i] in match.values():
                    return False
                # 如果单词没有出现在字典的值中,添加当前模式串与单词的对应关系
                match[pattern[i]] = word[i]
            else:
                # 如果当前模式串的键已经在字典中,检查字典的值和当前单词是否相等,不等返回False
                if match[pattern[i]] != word[i]:
                    return False
        return True


源代码文件在这里.


目录
相关文章
LeetCode 318. Maximum Product of Word Lengths
给定一个字符串数组 words,找到 length(word[i]) * length(word[j]) 的最大值,并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词,返回 0。
77 0
LeetCode 318. Maximum Product of Word Lengths
LeetCode 212. Word Search II
给定一个二维网格 board 和一个字典中的单词列表 words,找出所有同时在二维网格和字典中出现的单词。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
79 0
LeetCode 212. Word Search II
|
索引
LeetCode 79. Word Search
给定一个2D板和一个单词,找出该单词是否存在于网格中。 该单词可以由顺序相邻的单元的字母构成,其中“相邻”单元是水平或垂直相邻的单元。 相同的字母单元格不得多次使用。
73 0
LeetCode 79. Word Search
|
索引 存储
LeetCode 290 Word Pattern(单词模式)(istringstream、vector、map)(*)
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50611509 翻译 给定一个模式,和一个字符串str,返回str是否符合相同的模式。
956 0
LeetCode 58 Length of Last Word(最后单词的长度)
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50592917 翻译 给定一个包含大小写字母和空格字符的字符串, 返回该字符串中最后一个单词的长度。
727 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
107 2