string - 来自字符串数组的有效二叉树

Question

我有一个字符串数组。字符串中的每个字符只能是 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 开始考虑它的所有前缀并检查集合。如果集合中不存在任何前缀，那么我将返回 false。
我想知道是否有更优化的解决方案或对上述方法进行修改。

Answer 1

带有测试用例的递归方法，

public static void main(String[] args) {
    System.out.println(new Main().isValid(new String[]{"LRL", "LRR", "LL", "LR"}));
    System.out.println(new Main().isValid(new String[]{"LRL", "LRR", "LL", "LR", "L"}));
    System.out.println(new Main().isValid(new String[]{"LR", "L"}));
    System.out.println(new Main().isValid(new String[]{"L", "R", "LL", "LR"}));
}

public boolean isValid(String[] strs) {
    Set<String> set = new HashSet<>();
    int maxLength = 0;
    for (String str : strs) {
        set.add(str);
        maxLength = Math.max(str.length(), maxLength);
    }
    helper(set, "L", 1, maxLength);
    helper(set, "R", 1, maxLength);
    return set.isEmpty();
}

private void helper(Set<String> set, String current, int len, int maxLength) {
    if (!set.contains(current) || current.length() > maxLength) {
        return;
    }

    if (set.contains(current))
        set.remove(current);
    helper(set, current + "L", len + 1, maxLength);
    helper(set, current + "R", len + 1, maxLength);
}