Rust練習(xí)冊之字母異位詞與字符串處理方法技巧

更新時間：2026年02月04日 08:17:19 作者：一縷清煙在人間

Rust作為一種系統(tǒng)編程語言,其在字符串拼接方面的設(shè)計既靈活又高效,這篇文章主要介紹了Rust練習(xí)冊之字母異位詞與字符串處理方法技巧的相關(guān)資料,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下

前言

在日常生活中，我們經(jīng)常會遇到一些單詞，它們由相同的字母組成，但順序不同，這種詞被稱為"字母異位詞"(Anagram)。比如 “listen” 和 “silent” 就是一對字母異位詞。在 Exercism 的 “anagram” 練習(xí)中，我們將實現(xiàn)一個字母異位詞查找器，這不僅能幫助我們理解字符串處理的基本技巧，還能深入學(xué)習(xí) Rust 中的集合操作和字符處理。

問題背景

字母異位詞是指由相同字母重新排列組成的不同單詞。判斷兩個單詞是否為字母異位詞的核心思想是：如果兩個單詞包含完全相同的字母，且每個字母出現(xiàn)的次數(shù)也相同，那么它們就是字母異位詞。

讓我們先看看練習(xí)提供的實現(xiàn)：

use std::collections::HashSet;

fn sort(word: &str) -> String {
    let mut chars: Vec<char> = word.chars().collect();
    chars.sort_unstable();
    chars.into_iter().collect()
}

pub fn anagrams_for<'a>(word: &'a str, possible_anagrams: &'a [&str]) -> HashSet<&'a str> {
    let word = word.to_lowercase();
    let sorted = sort(&word);
    possible_anagrams
        .iter()
        .filter(|e| {
            let x = e.to_lowercase();
            x != word && sorted == sort(&x)
        })
        .cloned()
        .collect()
}

這個實現(xiàn)采用了非常優(yōu)雅的方法：將單詞中的字符排序，如果兩個單詞排序后相同，那么它們就是字母異位詞。

算法解析

1. 字符排序方法

fn sort(word: &str) -> String {
    let mut chars: Vec<char> = word.chars().collect();
    chars.sort_unstable();
    chars.into_iter().collect()
}

這個函數(shù)是整個算法的核心：

將字符串轉(zhuǎn)換為字符向量
對字符進(jìn)行排序
將排序后的字符重新組合成字符串

使用 sort_unstable 而不是 sort 是因為不需要穩(wěn)定排序，這樣可以獲得更好的性能。

2. 主要邏輯

pub fn anagrams_for<'a>(word: &'a str, possible_anagrams: &'a [&str]) -> HashSet<&'a str> {
    let word = word.to_lowercase();
    let sorted = sort(&word);
    possible_anagrams
        .iter()
        .filter(|e| {
            let x = e.to_lowercase();
            x != word && sorted == sort(&x)
        })
        .cloned()
        .collect()
}

主函數(shù)的邏輯非常清晰：

將目標(biāo)單詞轉(zhuǎn)為小寫并排序作為基準(zhǔn)
遍歷所有候選詞
過濾條件：
- 候選詞不能與目標(biāo)詞相同（即使大小寫不同）
- 候選詞排序后必須與目標(biāo)詞排序后相同
收集結(jié)果到 HashSet 中

測試用例分析

通過查看測試用例，我們可以更好地理解需求：

#[test]
fn test_no_matches() {
    let word = "diaper";

    let inputs = ["hello", "world", "zombies", "pants"];

    let outputs = vec![];

    process_anagram_case(word, &inputs, &outputs);
}

最基本的情況，沒有任何匹配的字母異位詞。

#[test]
fn test_detect_simple_anagram() {
    let word = "ant";

    let inputs = ["tan", "stand", "at"];

    let outputs = vec!["tan"];

    process_anagram_case(word, &inputs, &outputs);
}

簡單情況，“ant” 和 “tan” 是字母異位詞。

#[test]
fn test_case_insensitive_anagrams() {
    let word = "Orchestra";

    let inputs = ["cashregister", "Carthorse", "radishes"];

    let outputs = vec!["Carthorse"];

    process_anagram_case(word, &inputs, &outputs);
}

大小寫不敏感的匹配，“Orchestra” 和 “Carthorse” 是字母異位詞。

#[test]
fn test_does_not_detect_a_word_as_its_own_anagram() {
    let word = "banana";

    let inputs = ["banana"];

    let outputs = vec![];

    process_anagram_case(word, &inputs, &outputs);
}

一個詞不能是它自己的字母異位詞，即使大小寫不同。

#[test]
fn test_unicode_anagrams() {
    let word = "ΑΒΓ";

    // These words don't make sense, they're just greek letters cobbled together.
    let inputs = ["ΒΓΑ", "ΒΓΔ", "γβα"];

    let outputs = vec!["ΒΓΑ", "γβα"];

    process_anagram_case(word, &inputs, &outputs);
}

支持 Unicode 字符，包括希臘字母。

替代實現(xiàn)方法

除了字符排序方法，還有其他幾種判斷字母異位詞的方式：

1. 字符計數(shù)方法

use std::collections::HashMap;
use std::collections::HashSet;

fn char_count(word: &str) -> HashMap<char, usize> {
    let mut counts = HashMap::new();
    for c in word.chars() {
        *counts.entry(c).or_insert(0) += 1;
    }
    counts
}

pub fn anagrams_for<'a>(word: &'a str, possible_anagrams: &'a [&str]) -> HashSet<&'a str> {
    let word = word.to_lowercase();
    let word_counts = char_count(&word);
    
    possible_anagrams
        .iter()
        .filter(|&candidate| {
            let candidate_lower = candidate.to_lowercase();
            candidate_lower != word && char_count(&candidate_lower) == word_counts
        })
        .cloned()
        .collect()
}

這種方法通過統(tǒng)計每個字符出現(xiàn)的次數(shù)來判斷是否為字母異位詞。

2. 排序優(yōu)化版本

use std::collections::HashSet;

fn normalize(word: &str) -> String {
    let mut chars: Vec<char> = word.to_lowercase().chars().collect();
    chars.sort_unstable();
    chars.into_iter().collect()
}

pub fn anagrams_for<'a>(word: &'a str, possible_anagrams: &'a [&str]) -> HashSet<&'a str> {
    let normalized_target = normalize(word);
    let target_lower = word.to_lowercase();
    
    possible_anagrams
        .iter()
        .filter(|&&candidate| {
            let candidate_lower = candidate.to_lowercase();
            candidate_lower != target_lower && normalize(candidate) == normalized_target
        })
        .cloned()
        .collect()
}

這個版本在 normalize 函數(shù)中就進(jìn)行了小寫轉(zhuǎn)換，避免了重復(fù)轉(zhuǎn)換。

性能比較

讓我們分析一下不同方法的性能特點：

字符排序方法：
- 時間復(fù)雜度：O(n log n)，其中 n 是單詞長度
- 空間復(fù)雜度：O(n)
- 優(yōu)點：實現(xiàn)簡單，易于理解
- 缺點：排序操作相對較慢
字符計數(shù)方法：
- 時間復(fù)雜度：O(n)，其中 n 是單詞長度
- 空間復(fù)雜度：O(k)，其中 k 是不同字符的數(shù)量
- 優(yōu)點：時間復(fù)雜度更優(yōu)
- 缺點：需要額外的 HashMap 存儲

對于大多數(shù)實際應(yīng)用，字符排序方法已經(jīng)足夠快，而且代碼更簡潔。

邊界情況處理

在實現(xiàn)中需要特別注意以下邊界情況：

#[test]
fn test_misleading_unicode_anagrams() {
    // Despite what a human might think these words different letters, the input uses Greek A and B
    // while the list of potential anagrams uses Latin A and B.
    let word = "ΑΒΓ";  // 希臘字母

    let inputs = ["ABΓ"];  // 拉丁字母 + 希臘字母

    let outputs = vec![];

    process_anagram_case(word, &inputs, &outputs);
}

Unicode 字符的處理需要特別小心，因為看起來相似的字符可能有不同的編碼。

#[test]
fn test_same_bytes_different_chars() {
    let word = "a?"; // 61 E2 AC 82

    let inputs = ["€a"]; // E2 82 AC 61

    let outputs = vec![];

    process_anagram_case(word, &inputs, &outputs);
}

即使字節(jié)相同但字符順序不同也不能算作字母異位詞。

實際應(yīng)用場景

字母異位詞在實際開發(fā)中有多種應(yīng)用：

文本處理工具：查找文檔中的字母異位詞
游戲開發(fā)：拼字游戲中的單詞匹配
教育軟件：語言學(xué)習(xí)應(yīng)用中的練習(xí)題
數(shù)據(jù)清洗：識別重復(fù)但拼寫不同的數(shù)據(jù)項

擴展功能

基于這個基礎(chǔ)實現(xiàn)，我們可以添加更多功能：

use std::collections::HashSet;

pub struct AnagramSolver {
    word: String,
    sorted_chars: String,
}

impl AnagramSolver {
    pub fn new(word: &str) -> Self {
        let word = word.to_lowercase();
        let sorted_chars = Self::sort_chars(&word);
        AnagramSolver { word, sorted_chars }
    }
    
    fn sort_chars(word: &str) -> String {
        let mut chars: Vec<char> = word.chars().collect();
        chars.sort_unstable();
        chars.into_iter().collect()
    }
    
    pub fn is_anagram(&self, candidate: &str) -> bool {
        let candidate_lower = candidate.to_lowercase();
        candidate_lower != self.word && Self::sort_chars(&candidate_lower) == self.sorted_chars
    }
    
    pub fn find_anagrams<'a>(&self, candidates: &'a [&str]) -> HashSet<&'a str> {
        candidates
            .iter()
            .filter(|&&candidate| self.is_anagram(candidate))
            .cloned()
            .collect()
    }
}

這種面向?qū)ο蟮姆绞娇梢员苊庵貜?fù)計算目標(biāo)詞的排序結(jié)果。