如何在 Rust 中查找两个字符串是否有公共字符

Question

我刚开始学习rust，想知道两个字符串是否有共同的字符。我知道应该有一种简单的方法可以在不使用正则表达式的情况下实现（我不反对使用正则表达式）, 也许可以通过使用my_str.chars().any() 来实现，但我不确定如何执行。

以前我在Python中通过比较集合来完成这项任务。

if len(set(candidate) & set(required)) < 1: 

编辑

let result = candidate.chars().any(|c| required.contains(c));

所以，我能够使用any得到解决方案。但由于我对Rust不熟悉，我不确定这是否是最佳方法。也许使用HashSets会更有效率？我的应用程序很小，因此效率不是一个巨大的因素。什么是最“rustic”的方式？

- nalyd88

---

请问您能否更具体地说明您想要做什么，以及遇到了什么问题？在Python代码中为什么要将长度与1进行比较？您是否尝试过直接将Python代码翻译成Rust，如果有，是否遇到了任何问题？目前我还不太明白您的具体问题是什么。 - Sven Marnach

@MadWombat 我明白目标是什么，但我不明白具体的问题在哪里。Python代码可以比较直接地转换为Rust实现，但OP似乎遇到了一些障碍。当然，我可以写出代码（事实上我已经写了：https://play.rust-lang.org/?version=stable&mode=debug&edition=2015&gist=2c0332c1e65051f72fd4808a95b5d9ad），但如果我了解实际问题，我认为我可以给出更有用的答案。关于Python代码，我只是想知道为什么它以`< 1结尾而不是!= 0`。 - Sven Marnach

@PitaJ 在编写 Python 代码时，我通常更关心的是简洁易读而非性能，不过你说得对。 :) - Sven Marnach

你的解决方案时间复杂度为O(mn),其中_m_和_n_分别是两个字符串的长度。 使用集合的解决方案具有O(m + n)（摊销）复杂度，因此在渐近意义下要快得多。 对于非常短的字符串，它甚至可能稍微慢一些。 - Sven Marnach

如果可能出现的字符范围保证很小，您可以使用位数组来记录是否在第一个字符串中看到了一个字符，然后检查第二个数组中的每个字符的位数组。 - Chai T. Rex

Answer 1

你可以采用几种方法，这里提供了两个选项：

• 构建第一个字符串的一组字符，并检查第二个字符串是否包含该组字符中的任何一个[O(n + m)]
• 迭代第一个字符串的字符，并检查第二个字符串是否包含其中任何一个[O(n * m)]

我决定使用HashSet，但如果你只关心ascii（因此限制在256个可能性内），你可以使用基本数组。

use std::collections::HashSet;

fn share_char(a: &str, b: &str) -> bool {
    // get which one is shorter
    let (shorter, longer) = if a.len() > b.len() {
        (b, a)
    }  else {
        (a, b)
    };

    // fill the set with the characters from the shorter string
    let set: HashSet<char> = shorter.chars().collect();

    longer.chars().any(|c| set.contains(&c))
}

#[test]
fn test() {
    let str1 = "abcdef";
    let str2 = "the quick brown fox";
    let str3 = "hijk";

    assert!(share_char(str1, str2));
    assert!(!share_char(str1, str3));
}

https://play.rust-lang.org/?version=stable&mode=debug&edition=2015&gist=76567b94d3bd15b37e33acb9a8d701d5

编辑：改用collect。

编辑2：我想解释一下为什么我做了较短/较长的检查，以及为什么我没有建立两个集合。

将元素插入到HashSet中比仅迭代字符串的字符更耗费资源。这意味着从长字符串构建集合与从短字符串构建集合之间存在差异。很可能这种差异是可以忽略不计的，因为您的字符串长度很可能相似。

这种资源消耗的差异也是我不建立第二个集合的原因。我们不仅节省了插入成本，还可以节省一些迭代次数，因为如果找到匹配项，我们的any将会短路。

编辑3：另外，如果您只想检查一个字符串是否包含给定字符集中的任何字符，则应使用模式匹配。

str1.chars().any(|c| match c {
    'a' | 'd' | 'f' | 'e' => true,
    _ => false,
});

这将比使用静态Set甚至更高效。

- PitaJ

Answer 2

.any + .contains 的意思是从一个字符串中迭代每个字符，以检查是否包含另一个字符串中的所有元素（复杂度为O(nm)）;

---

相反，您可以使用哈希映射将每个字符作为键，并将布尔值或整数作为值：
在这种情况下，您需要在第一次迭代中存储第一个字符串中的所有字符，然后迭代第二个字符串，尝试从哈希映射中获取每个字符。
如果存在该字符，则立即返回true（最坏情况下的复杂度为O(n+m)）。

---

为了提高性能，建议在可能的情况下使用数组代替HashMap，并将键表示为索引。

fn common_chars(s1: &str, s2: &str) -> bool {
   const ALPHABET_LEN: usize = 26;
   const CHAR_CODE: usize = 97; // a-97, z-122
   let mut alpahbet = [0; ALPHABET_LEN]; 
   for c in s1.chars() {
      alpahbet[c as usize - CHAR_CODE] += 1; // store each char from first string
   }
   for c in s2.chars() {
      if alpahbet[c as usize - CHAR_CODE] != 0 { // a stored char is found!
         return true;
      }
   }
   false
}
#[test]
fn test() {
   let str1 = "abcdef";
   let str2 = "the quick brown fox";
   let str3 = "hijk";
   assert!(common_chars(str1, str2));
   assert!(!common_chars(str1, str3));
}

- artem

---

请避免仅提供代码答案，并解释其工作原理，为什么它更有效率？ - Mickael B.