看懂“单词规律”的算法之美：为什么简单的模式匹配，其实很深

看懂“单词规律”的算法之美：为什么简单的模式匹配，其实很深

作者：Echo_Wish

有时候做算法久了，你会发现一个挺有意思的事情：很多看起来很简单的题，其实背后藏着很深的思想。

比如今天要聊的这个题 ——Word Pattern（单词规律）。

题目本身其实很简单：

给定一个字符串pattern和一个字符串s，判断s是否遵循相同的模式。

举个例子：

pattern = "abba" s = "dog cat cat dog"

返回：

true

因为：

a → dog b → cat b → cat a → dog

映射是稳定的。

但如果是：

pattern = "abba" s = "dog cat cat fish"

那就不行了，因为：

a → dog b → cat b → cat a → fish

a之前是dog，现在变成fish了。

表面看这是一个字符串题，但实际上它背后在考察一个非常经典的思想：