java - 棘手的 Java 字符串面试问题。给定 List 和 char [] 返回仅包含 char [] 的最长字符串

Question

给定一个字符串列表和一个字符数组，返回仅包含数组中字符的最长字符串。

我很确定我把它冲洗干净了。我的第一直觉是使用正则表达式，但我认为没有人第一次就正确使用正则表达式并且不查找任何内容。

是否有使用按位运算符或其他方式执行此操作的棘手方法？

Answer 1

一个想法是转换 char[]到 Set<Character>对于 O(1) 包含测试，然后简单地遍历字符串列表并检查每个特定字符串是否仅包含上述集合中的字符，跟踪您使用此属性找到的最长字符串。

如果你有更多的信息，你可以做更多的优化。例如，如果字符串本身很长但列表不是，那么首先按长度对列表进行排序可能会有所帮助，然后首先开始处理最长的字符串。

---

Is there a tricky way of doing this using bitwise operators or something?

如果您对可以包含在 char[] 中的字符范围有某种(小的)限制, 然后你可以将整个事情编码在一个 int 中/long ，这将替代 Set<Character>我在上面提到过。例如，假设只有来自 'a' 的字符至 'z'将包含在内，那么我们可以按如下方式进行编码:

long charset = 0;

for (char c : chars) {
    charset |= (1 << (c - 'a'));
}

现在，检查某个字符是否为 c包含在原始 char[] 中，我们可以简单地使用:

if ((charset & (1 << (c - 'a'))) != 0) {
    // c was in the original char[]
}