题目大意：

有一个字符串它的构成是词 + 空格的组合，如“北京 杭州 杭州 北京”,

要求输入一个匹配模式（简单的以字符来写）， 比如 aabb, 来判断该字符串是否符合该模式。

例子：

pattern = "abba", str="北京 杭州 杭州 北京" 返回 ture

pattern = "aabb", str="北京 杭州 杭州 北京" 返回 false

pattern = "abc", str="北京 杭州 杭州 南京" 返回 false

pattern = "acac", str="北京 杭州 北京 广州" 返回 false

编程语言：Java

1. 参考思路

对于 pattern，我们需要将其由字符串拆分成字符数组，该数组中的每一个字符都需要对应 str 中的一个词。

也就是说，pattern.length 和 str.split(" ").length 是务必要相等的。我们可以把这一前提当做算法最开始的校验条件，以下不再赘述。

1.1 解法一

对于 pattern 拆分而来的字符数组，如：[a, b, b, a]，和目标字符串 str 按空格拆分出的单词数组，如：[北京, 杭州, 杭州, 北京]，不难推理出，a、b 实际需要对应的单词，是根据第一次出现 a、b 时，其所对应的单词而定的。

那么，我们就可以将这个问题的解法转换为：

从左到右同时遍历字符数组和单词数组，并在该过程中：

1. 当 pattern 字符数组第一次出现某一字符时，根据其在单词数组中的位置，记录该字符对应的单词；
2. 当 pattern 字符数组第 N 次（ N > 1 ）出现某一字符时，取出该字符应该对应的单词，并与当前字符对应在单词数组中的单词对比，如果相同则继续校验，否则返回 false；
3. 如果校验至最后一个单次仍然成立，则返回 true。

那么，又延伸出两个问题：

1. 如果知道字符是不是第一次出现呢？
2. 如何记录某一字符所对应的单词呢？

借助 Hash 数据结构，这两个问题可以同时得到解决，假设我们有一个 HashMap<String, String> 类型的变量 hashMap，对于当前遍历到的字符 c，和同位置的单词 W：

1. 通过 hashMap.get(c) == null 来判定字符是否为第一次出现；
2. 如果是第一次出现，则通过 hashMap.put(c, W) 将该字符对应的单次记录下来；
3. 如果不是第一次出现，则通过 hashMap.get(c) 将其取出，并与 W 进行比较。

1.2 解法二

每次看到字符串匹配，总是不自觉的想到正则表达式。

比如，对于题目中所说的 abba 匹配，其实就相当于正则表达式：^([^\s]+)\s\1\s([^\s]+)\s\2$。这里用到了正则中捕获组和反向引用的内容，详情可参考：

同样的，解法思路为：

1. 当字符第一次出现时，为正则字符串增加 ([^\s]+)，即被捕获组包裹的除空格以外的、长度大于 1 的字符串，并记录该字符对应的反向引用的索引，即第几个捕获组（ 序号从 1 开始 ）；
2. 当字符第二次出现时，根据 1 中记录的捕获组索引 n，为正则增加反向引用 \n

当然，由于目标字符串中的单词使用了空格进行分割，每一小块正则之间需要加上 \s。此外，正则的首尾也需要补充相应符号。

2. 参考代码

个人觉得第二种解法比较有趣，下面贴出第二种解法的核心代码：

public static void main(String[] args) {    if (args.length < 2) {        logger.info("@@@@ 用法：
     
     
      ");        System.exit(1);    }    // 用 model 表示用户指定的「模式」    // 用 pattern 表示正则    String modelStr = args[0];    String target = args[1];    logger.info("@@@@ 匹配模式为：" + modelStr + "，测试内容为：" + target);    final String regexAnyWithoutSpace = "([^\\s]+)";    final String regexSpace = "\\s";    // key 为字符，value 为反向引用序号，用于构造正则表达式    Map
      
        regexPlaceholderIndexMap = new HashMap<>();    // 正则中，反向引用序号从 1 开始    Integer regexPlaceholderIndex = 1;    // 生成正则表达式    List
       
         regexPatternArray = new ArrayList<>();    Integer patternLength = modelStr.length();    for (Integer index = 0; index < patternLength; index++) {        String needle = new String(new char[]{modelStr.charAt(index)});        Integer currentPlaceHolderIndex = regexPlaceholderIndexMap.get(needle);        if (currentPlaceHolderIndex == null) {            // 如果为空，证明这一字符刚刚出现            regexPatternArray.add(regexAnyWithoutSpace);            regexPlaceholderIndexMap.put(needle, regexPlaceholderIndex);            regexPlaceholderIndex++;        } else {            // 如果不为空，则证明为先前的某一字符，需用反向引用方式指代            regexPatternArray.add(String.format("\\%d", currentPlaceHolderIndex));        }    }    // 将正则各个部分用空格串起来，与需求匹配    // 并为其增加头尾限制    String patternStr = String.format("^%s$", String.join(regexSpace, regexPatternArray));    logger.info("@@@@ 组装的正则表达式为：" + patternStr);    Pattern pattern = Pattern.compile(patternStr);    Boolean isMatch = pattern.matcher(target).find();    logger.info("@@@@ 字符串匹配结果为：" + isMatch);}
       
      
     
    

代码 Gist 地址：

参考链接