新手求问怎么在String内交换两个元素，类似swap(s[i], s[j])?

eweca 发表于 2020-07-29 13:10

Tags：swap

假设：字符串在ASCII范围内。我尝试过:

    let mut s = String::new("abc");
    let temp = &s[0..1];
    s[0..1] = s[1..2];
    s[1..2] = temp;

但是会提示s[1..2]在编译时size未知。或许需要分成三段来拼接字符串？

好吧，我自己找到了个办法：

    let mut s = String::from("abc");  
    let temp = &s[0..1].to_string();
    s.replace_range(0..1, &s[1..2].to_string());
    s.replace_range(1..2, temp);

但是我还想知道，比较主流的做法是啥呢？

这题实际上是力扣的全排列题目，最后代码如下 (400~430 ms):

fn main() {
    let mut s = "ABCDEFGHIJ".to_string();
    let ans = Solution::permutation(s);
}


struct Solution;

impl Solution {
    pub fn permutation(s: String) -> Vec<String> {
        let mut res = vec![];
        let mut s = s.chars().collect();
        dfs(&mut s, 0, &mut res);

        res
    }
}


fn dfs(s: &mut Vec<char>, left: usize, res: &mut Vec<String>) {
    if left == s.len() {
        res.push(s.iter().collect());
    }

    for i in left..s.len() {
        s.swap(i, left);
        dfs(s, left+1, res);
        s.swap(i, left);
    }
}

感谢各位大神的指导！

评论区

写评论

作者 eweca 2020-07-30 01:17

方法可行！速度跟第一位答主的差不多。都属于T1的效率行列。

--
👇
kkonghao: 可以这样实现 let c = "china".to_string(); let mut d = c.into_bytes();

unsafe {
    ptr::swap(&mut d[0], &mut d[1]);
}

let ss = String::from_utf8(d).unwrap();
println!("{:?}", ss);

作者 eweca 2020-07-30 01:07

学习到了！这次按照你的说法，递归的时候直接传 &mut Vec而不是&mut String，速度和unsafe下那个速度一致。稍稍略慢于C++使用了原生swap的递归（5%左右）。而且可以不用unsafe！

--
👇
gwy15: 如果你只是全排列，应该直接用 Vec<char> 或者 Vec<u8>，最后再 collect 一遍。

kkonghao 2020-07-29 18:11

可以这样实现 let c = "china".to_string(); let mut d = c.into_bytes();

unsafe {
    ptr::swap(&mut d[0], &mut d[1]);
}

let ss = String::from_utf8(d).unwrap();
println!("{:?}", ss);

gwy15 2020-07-29 16:12

如果你只是全排列，应该直接用 Vec<char> 或者 Vec<u8>，最后再 collect 一遍。

作者 eweca 2020-07-29 14:36

感谢你的思路！

--
👇
gwy15: 因为 String 是 utf8 变长储存的，所以直接 swap byte 肯定是 unsafe 的，只能 swap char； swap char 最坏是 O(n) 的。

目前 swap char 没有对应的 API（确实不常见），replace_range 应该是最接近的了。也可以这么写：

let s = String::from("wello, Horld!");
let mut chars: Vec<char> = s.chars().collect();
chars.swap(0, 7);
let s: String = chars.into_iter().collect();

O(n), safe

作者 eweca 2020-07-29 14:35

可用！但是会比replace_range慢了不少（在我的算例，递归式dfs全排列String，里慢了50%）。

--
👇
gwy15: 因为 String 是 utf8 变长储存的，所以直接 swap byte 肯定是 unsafe 的，只能 swap char； swap char 最坏是 O(n) 的。

目前 swap char 没有对应的 API（确实不常见），replace_range 应该是最接近的了。也可以这么写：

let s = String::from("wello, Horld!");
let mut chars: Vec<char> = s.chars().collect();
chars.swap(0, 7);
let s: String = chars.into_iter().collect();

O(n), safe

作者 eweca 2020-07-29 14:33

感谢，这个方式非常之快。比replace_range快一倍。

--
👇
cnwzhjs: ```rust fn main() { let mut s = String::from("abc"); unsafe { s.as_mut_vec().swap(0, 1); } println!("{}", s); }


这也是一个方法……

cnwzhjs 2020-07-29 14:00

要不要去发个pr，把 String::swap 和 String::swap_range 加进去 :)

--
👇
gwy15: 因为 String 是 utf8 变长储存的，所以直接 swap byte 肯定是 unsafe 的，只能 swap char； swap char 最坏是 O(n) 的。

目前 swap char 没有对应的 API（确实不常见），replace_range 应该是最接近的了。也可以这么写：

let s = String::from("wello, Horld!");
let mut chars: Vec<char> = s.chars().collect();
chars.swap(0, 7);
let s: String = chars.into_iter().collect();

O(n), safe

gwy15 2020-07-29 13:55

因为 String 是 utf8 变长储存的，所以直接 swap byte 肯定是 unsafe 的，只能 swap char； swap char 最坏是 O(n) 的。

目前 swap char 没有对应的 API（确实不常见），replace_range 应该是最接近的了。也可以这么写：

let s = String::from("wello, Horld!");
let mut chars: Vec<char> = s.chars().collect();
chars.swap(0, 7);
let s: String = chars.into_iter().collect();

O(n), safe

cnwzhjs 2020-07-29 13:44

fn main() {
    let mut s = String::from("abc");
    unsafe { s.as_mut_vec().swap(0, 1); }
    println!("{}", s);
}

这也是一个方法……

1 共 10 条评论, 1 页