当模式遇上语言：聊聊《Word Pattern II》背后的算法之美

当模式遇上语言：聊聊《Word Pattern II》背后的算法之美

作者：Echo_Wish

做算法这么多年，我越来越觉得一件事特别有意思：

很多看起来很“计算机”的问题，其实本质是语言学问题。

比如今天要聊的这个经典题目：

Word Pattern II（单词规律 II）

乍一看，这题像字符串处理；
再仔细一看，它其实是：

模式匹配 + 回溯搜索 + 双向映射约束

如果说普通字符串匹配像“找字”，
那 Word Pattern II 更像是在做一件事：

给语言建立一种“规则”。

今天我们就用比较接地气的方式，一步一步拆开这道题。

一、题目到底在问什么？

先看一个简单例子。

pattern = "abab" s = "redblueredblue"

输出：

True

为什么？

因为可以建立这样的映射关系：