Rust实现字符替换全组合生成函数的问题及优化诉求

原代码的问题分析 #

1. 类型不匹配：你定义的返回类型是Vec<&String>，但实际生成的是Vec<String>。Rust不允许返回局部变量的引用（会导致悬垂引用），正确的返回类型应该是Vec<String>，直接持有字符串所有权。
2. 逻辑错误：代码中查找的是'J'而非需求的'X'；同时循环条件依赖最后一个元素的X位置，无法正确处理多轮替换场景。
3. 冗余循环：嵌套的for循环和while循环导致代码可读性差。

修正后的循环版本 #

fn every_combination(hand: &str) -> Vec<String> {
    let mut combinations = vec![hand.to_string()];

    loop {
        // 检查是否还有未替换的X
        let has_unreplaced_x = combinations.iter().any(|s| s.contains('X'));
        if !has_unreplaced_x {
            break;
        }

        let mut new_combinations = Vec::new();
        for s in combinations {
            if let Some(pos) = s.find('X') {
                // 对当前字符串的第一个X替换所有数字
                for digit in '0'..='9' {
                    let mut new_s = s.clone();
                    new_s.replace_range(pos..pos + 1, &digit.to_string());
                    new_combinations.push(new_s);
                }
            } else {
                // 无X的字符串直接保留
                new_combinations.push(s);
            }
        }

        combinations = new_combinations;
    }

    combinations
}

更优雅的递归实现 #

递归版本通过分解问题简化逻辑：每次找到第一个X，替换为0-9的每个数字后，递归处理剩余字符串，最后合并所有结果。

fn every_combination_recursive(hand: &str) -> Vec<String> {
    match hand.find('X') {
        // 没有X时直接返回原字符串的拷贝
        None => vec![hand.to_string()],
        Some(pos) => {
            let prefix = &hand[0..pos];
            let suffix = &hand[pos + 1..];
            // 对每个数字替换X后，递归处理并收集所有结果
            ('0'..='9')
                .flat_map(|digit| {
                    let base = format!("{prefix}{digit}{suffix}");
                    every_combination_recursive(&base)
                })
                .collect()
        }
    }
}

高效的迭代器实现 #

此版本先定位所有X的位置，再生成所有可能的数字组合，一次性完成替换，避免多层嵌套循环：

fn every_combination_iter(hand: &str) -> Vec<String> {
    // 收集所有X的索引位置
    let x_positions: Vec<usize> = hand
        .chars()
        .enumerate()
        .filter(|&(_, c)| c == 'X')
        .map(|(idx, _)| idx)
        .collect();

    let x_count = x_positions.len();
    if x_count == 0 {
        return vec![hand.to_string()];
    }

    // 生成0到10^x_count -1的所有数字，格式化为补0的固定长度字符串
    (0..10usize.pow(x_count as u32))
        .map(|num| {
            let digits = format!("{:0x_count$}", num);
            let mut chars: Vec<char> = hand.chars().collect();
            // 将数字组合依次替换到X的位置
            for (digit_idx, &x_pos) in x_positions.iter().enumerate() {
                chars[x_pos] = digits.chars().nth(digit_idx).unwrap();
            }
            chars.into_iter().collect()
        })
        .collect()
}

内容的提问来源于stack exchange，提问作者Be Chiller Too