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

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

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

前言

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

問題背景

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

讓我們先看看練習(xí)提供的實(shí)現(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()
}

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

算法解析

1. 字符排序方法

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

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

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

使用 sort_unstable 而不是 sort 是因?yàn)椴恍枰€(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 中

測(cè)試用例分析

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

#[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);
}

簡(jiǎn)單情況，“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);
}

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

#[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 字符，包括希臘字母。

替代實(shí)現(xiàn)方法

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

1. 字符計(jì)數(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)計(jì)每個(gè)字符出現(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()
}

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

性能比較

讓我們分析一下不同方法的性能特點(diǎn)：

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

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

邊界情況處理

在實(shí)現(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 字符的處理需要特別小心，因?yàn)榭雌饋硐嗨频淖址赡苡胁煌木幋a。

#[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é)相同但字符順序不同也不能算作字母異位詞。

實(shí)際應(yīng)用場(chǎng)景

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

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

擴(kuò)展功能

基于這個(gè)基礎(chǔ)實(shí)現(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ù)計(jì)算目標(biāo)詞的排序結(jié)果。

總結(jié)

通過 anagram 練習(xí)，我們學(xué)到了：

字符串處理：掌握了 Rust 中字符串和字符的基本操作
算法思維：學(xué)會(huì)了用排序和字符統(tǒng)計(jì)兩種方法解決同一問題
集合操作：熟練使用 HashSet 進(jìn)行數(shù)據(jù)收集和去重
生命周期：理解了 Rust 中的生命周期注解
Unicode 處理：了解了 Unicode 字符的復(fù)雜性
測(cè)試驅(qū)動(dòng)：通過豐富的測(cè)試用例確保實(shí)現(xiàn)的正確性

這些技能在實(shí)際開發(fā)中非常有用，特別是在處理文本數(shù)據(jù)、實(shí)現(xiàn)搜索功能和構(gòu)建語言相關(guān)應(yīng)用時(shí)。字母異位詞雖然看起來簡(jiǎn)單，但它涉及到了字符串處理的許多核心概念，是學(xué)習(xí) Rust 字符串操作的良好起點(diǎn)。

到此這篇關(guān)于Rust練習(xí)冊(cè)之字母異位詞與字符串處理方法技巧的文章就介紹到這了,更多相關(guān)Rust字母異位詞與字符串內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: