算法题解 | Rust 字符串处理：替换所有问号

张汉东

发布于 2020-12-15 11:27:59

1.7K0

发布于 2020-12-15 11:27:59

文章被收录于专栏：Rust 编程

题号：Leetcode #1576

题目要求：

替换所有包含的'?'字符。
替换后不能有重复的字母存在。
最终返回字符串。

思路梳理：

为了性能，最好原地修改字符串。

Rust 有两种方式处理字符串，一种是按字节，一种是按字符。

我们选择按字符处理，这道题的结构至少是下面这样：

impl Solution {
    pub fn modify_string(s: String) -> String {
        let mut chars = s.chars().collect::<Vec<char>>();
        
        // 处理字符串
        
        chars.into_iter().collect::<String>()
    }
}

对传入的字符串转换为字符数组，然后将处理后的字符数组转为字符串。通过迭代器可以顺利完成这两步。

接下来就是要迭代处理字符了。

// 使用 迭代器方法 `enumerate()` 可以在迭代的时候使用 index
    // 此处记得要 使用 `.iter_mut` 方法对chars进行可变借用，因为我们要原地替换字符。
    // 如果不对`chars`进行借用，在最后转换为String字符串的时候，`chars`因为被Move了，就不能使用了。
    for (i, c) in chars.iter_mut().enumerate() {
        // 定义 a-z 字母集
        let mut words = ('a'..='z').into_iter();
        // 此处 `chars[i]` 是对chars的不可变借用
        if chars[i] == '?' {
            // 此处 `chars[i]` 是对chars的不可变借用
            let left = if i==0 {None} else { Some(chars[i-1]) };
            // 此处 `chars[i]` 是对chars的不可变借用
            let right = if i==s.len()-1 {None} else {Some(chars[i+1])};
            // 此处 `chars[i]` 是对chars的可变借用，要修改chars数组了
            // 从a-z 字母集中查找和左右两边不一样的字母去替换当前字符，避免重复
            chars[i] = words.find(|&w| Some(w) != left && Some(w) != right).unwrap();
        }
    }

这段代码思路上没有问题，但是，因为 Rust 语言的借用检查，会报错：

error[E0502]: cannot borrow `chars` as immutable because it is also borrowed as mutable  --> src/main.rs:16:51   |10 |     for (i, c) in chars.iter_mut().enumerate() {   |                   ----------------------------   |                   |   |                   mutable borrow occurs here   |                   mutable borrow later used here...16 |             let left = if i==0 {None} else { Some(chars[i-1]) };   |                                                   ^^^^^ immutable borrow occurs hereerror[E0499]: cannot borrow `chars` as mutable more than once at a time  --> src/main.rs:18:13   |10 |     for (i, c) in chars.iter_mut().enumerate() {   |                   ----------------------------   |                   |   |                   first mutable borrow occurs here   |                   first borrow later used here...18 |             chars[i] = words.find(|&w| Some(w) != left && Some(w) != right).unwrap();   |             ^^^^^ second mutable borrow occurs here

借用检查不允许我们在对chars可变借用的同时，又对chars进行不可变借用。并且还借用两次可变借用。不可变借用和可变借用的生命周期重叠了，所以需要修改一下：

for i in 0..s.len() {      
  // 定义 a-z 字母集        
  let mut words = ('a'..='z').into_iter();        
  // 此处 `chars[i]` 是对chars的不可变借用        
  if chars[i] == '?' {            
  // 此处 `chars[i]` 是对chars的不可变借用            
  let left = if i==0 {None} else { Some(chars[i-1]) };            
  // 此处 `chars[i]` 是对chars的不可变借用            
  let right = if i==s.len()-1 {None} else {Some(chars[i+1])};            
  // 此处 `chars[i]` 是对chars的可变借用，要修改chars数组了            
  // 从a-z 字母集中查找和左右两边不一样的字母去替换当前字符，避免重复            
  chars[i] = words.find(|&w| Some(w) != left && Some(w) != right).unwrap();        
}

这样，代码就可以通过了。因为不可变借用生命周期和可变借用生命周期并没有重叠，所以编译没有问题。

但是有问题的是 if 表达式中最后一行：

chars[i] = words.find(|&w| Some(w) != left && Some(w) != right).unwrap();

虽然这个 unwrap() 在当前是没有风险的，因为 words.find(|&w| Some(w) != left && Some(w) != right) 的值不太可能返回None。但是一个更优雅的写法是：‍

if let Some(w) = words.find(|&w| Some(w) != left && Some(w) != right) {        chars[i] = w;    }

最终代码

impl Solution {
    pub fn modify_string(s: String) -> String {
        let mut chars = s.chars().collect::<Vec<char>>();
        
        for i in 0..s.len()  {
            let mut words = ('a'..='z').into_iter();
            if chars[i] == '?' {
                let left = if i==0 {None} else { Some(chars[i-1]) };
                let right = if i==s.len()-1 {None} else {Some(chars[i+1])};
                let res = words.find(|&w| Some(w) != left && Some(w) != right);
                if let Some(w) = res { chars[i] = w; }
            }
        }
        
        chars.into_iter().collect::<String>()
    }
}

用时 0 ms，空间占用 1.9 MB。

然而，同样的代码，多次提交的结果空间占用不太一致，大概在 1.9~2.2MB 范围幅动。

你喜欢这篇题解吗？

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-12-04，如有侵权请联系 cloudcommunity@tencent.com 删除

rust