今天向大家介绍一种特殊的属性结构的应用，主要是介绍几个相关的题目的分析思路及相关实现。
题目1的描述见参考引文1，为了实现方便起见，Trie树中的单词都是小写英文中的26个字母。参考引文1的网页右边同时提供了一种基于递归的实现，同时求字符字串使用的是std::string类的substr函数（需要注意一下这个函数的参数的含义，第一个参数表示字串起始位置，第二个参数表示字串长度，而不是字串终止位置）。但是这个问题的推荐解法请参考引文2，相对第一种实现有两个地方的明显改进，第一个地方在于通过“for (char ch : word)”访问字符串的每一个单词，而且通过for方式避免了递归调用函数，节省了系统的执行资源。
题目2的要求是添加和搜索单词，具体描述参考引文3，这道题目在上述的基础上做了一定的扩展，支持通配符，需要注意一些边界条件，稍不注意就容易在某些情况出现bug。同时为了应对通配符的情况，代码中某些地方用到了递归调用。总体上也是一种扩展的前缀树应用，具体实现可以参考引文3网页的右边的代码。
题目3的详细描述请见参考引文4，这道题目的要求是已经有词汇表，根据矩形单词盘板的字母排列规则去核实词汇表中的哪些单词可以从矩形单词盘板中排列（字母之间只能和上下左右相连）得出。这里给出我的思路（欢迎读者给出更加高效的解决方案），首先通过按照题目1或2的方法根据词汇表去构建前缀树（一种特殊构造的词汇表），然后根据从矩形框中的每一个位置进行上下左右四个方向的搜索（需要考虑矩形的边界情况进行剪枝），可以理解为对一颗四叉树进行深度优先搜索，参考引文6提供了一个实现，这里也是一种回溯算法，在代码实现的过程中需要考虑回溯状态的复位。
引文5提供了上述三个问题的各一种解决方法，在前面的部分代码没有充分的从效率上进行优化，不过也可以从三个题目中去互相借鉴更优的写法。
References
Leave a Reply