我有一个字符串数组 . 字符串中的每个字符只能是r或l . 我必须检查它是否有效
1. {rlr,l,r,lr, rl}
*
/ \
l r
\ /
r l
\
r
A valid tree as all nodes are present.
2. {ll, r, rl, rr}
*
/ \
- r
/ /\
l l r
Invalid tree as there is no l node.
从给定输入我必须确定它是否正在创建有效的树 . 我想出了两个解决方案 .
1.使用trie存储输入并在插入时将每个节点标记为有效 .
2.根据长度排序输入数组 . 所以对于第一种情况，它将是{l，r，lr，rl，rlr}
我将创建一组字符串来放置所有输入 . 如果一个字符串的长度大于1（对于rlr :: r，rl），我将从索引0开始考虑它的所有前缀，并检查set.if中不存在的任何前缀，然后我将返回false .
我想知道在上述方法中是否有更优化的解决方案或任何修改 .
1 回答
另一种可能的解决方案实际上是构建树（或trie）并维护一组尚未完成的节点 .
如果完成对列表的迭代，但仍然有不完整的节点，那么树无效 .
如果集合为空，则树有效 .
例如，在您给出的第二个树中，对于节点
ll，您还将创建节点l，但您将其添加到不完整的集合中 . 如果后面的某个节点是l，那么您将从集合中删除它 . 如果没有，您将使用包含缺少节点的非空集结束迭代 .