本文主要是介绍《你也能看得懂的Python算法书》学习笔记（二），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
学习笔记（一）讲解了一道经典的两数之和问题，学习笔记（二）将讲解另外一道使用哈希算法求解的经典例题。
一、单词模式匹配
题目：首先给定两个字符串，一个是单词模式字符串，另一个是目标字符串。之后检查目标字符串是否是给定的单词模式，即求目标字符串中单词出现的规律是否符合单词模式字符串的单词出现的规律。例如：单词模式字符串为‘1221’，目标字符串可以是'apple banana banana apple'，字符串为‘apple apple banana banana’（1122）使用模式字符串‘1221’则匹配不成功。
求解思路：首先我们要明确映射的种类，映射分为（一对一，一对多，和多对多的关系）。在例子1221（apple banana banana apple)中，映射关系是一对一的。即1-apple，2-banana，除此之外没有其他的关系。在例子‘apple apple banana banana’使用模式字符串‘1221’中我们可以发现1-apple bear，2-apple bear出现了多对多的映射情况，所以匹配不成功。因此我们可以发现，如果只存在一对一的映射关系则匹配成功。这样其实我们的任务就变成了查找映射关系的问题。哈希表可以存储映射关系，因此本题我们可以利用哈希表来求解。
def wordpattern(wordpart,input):word = input.split(" ")if len(word) != len(wordpart): # 排除长度不同的情况return Falsehash = {}used = {}for i in range(len(wordpart)):if wordpart[i] in hash:if hash[wordpart[i]] != word[i]:return Falseelse:if word[i] in used:return Falsehash[wordpart[i]] = word[i]used[word[i]] = Trueprint(hash)print(used)return True在代码中我们可以看到我们建立了两个哈希表：hash和used。hash用来储存模式字符串和目标字符串的对应关系，used记录目前已经使用的字符串。
解决第一个问题，模式字符串中每个字符只能对应目标字符串一个单词。因此我们每次拿到模式字符串中的一个字符的时候，需要检查一下它是否已经有过映射关系，如果有映射关系需要检查之前映射关系对应的单词和这次的单词是否一致，如果不一致则返回False，如果是第一次出现则把它存储在哈希表中。
for i in range(len(wordpart)):if wordpart[i] in hash:if hash[wordpart[i]] != word[i]:return Falseelse:if word[i] in used:return False解决第二个问题，当模式字符串中的某个字符第一次出现时，还需要判断这个单词是否已经和其他的模式字符绑定，这是需要用到used哈希表。每当创建一种映射关系的时候，都需要在used中保存，同时还要检查这个单词是否已经使用过。
for i in range(len(wordpart)):if wordpart[i] in hash:if hash[wordpart[i]] != word[i]:return Falseelse:if word[i] in used:return Falsehash[wordpart[i]] = word[i]used[word[i]] = True这篇关于《你也能看得懂的Python算法书》学习笔记（二）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
