英文:
Rust lifetimes: these two types are declared with different lifetimes
问题
Here is the translated code:
我正在学习Rust中的字符串。我想要实现一个函数来计算字符串列表中的最长公共前缀。我的代码impl Solution {pub fn get_common_prefix(s1: &String, s2: &String) -> String {let mut idx: usize = 0;if s1.len() > s2.len() {std::mem::swap(&mut s1, &mut s2);}while idx < s1.len() && s1.chars().nth(idx) == s2.chars().nth(idx) {idx += 1;}return s1[0..idx].to_string();}pub fn longest_common_prefix(mut strs: Vec<String>) -> String {strs.sort();let mut longest_pref = strs[0].clone();for i in 0..strs.len() {longest_pref = Self::get_common_prefix(&longest_pref, &strs[i]);}return longest_pref;}}
Regarding the error you mentioned, it seems to be a lifetime mismatch issue. You can fix it by cloning the strings in your longest_common_prefix function. I've made that change in the translated code above by using .clone(). This should resolve the error.
英文:
I am learning strings in Rust. I want to implement function to calculate the longes common prefix among list of strings.
My code
impl Solution {pub fn get_common_prefix(s1: &String, s2: &String) -> String {let mut idx: usize = 0;if s1.len() > s2.len() {std::mem::swap(&mut s1, &mut s2);}while idx < s1.len() && s1.chars().nth(idx) == s2.chars().nth(idx) {idx += 1;}return s1[0..idx].to_string();}pub fn longest_common_prefix(mut strs: Vec<String>) -> String {strs.sort();let mut longest_pref = strs[0];for i in 0..strs.len() {longest_pref = Self::get_common_prefix(&longest_pref, &strs[i]);}return longest_pref;}}
I have an error. Could you please help to fix it?
Line 5, Char 37: lifetime mismatch (solution.rs)|2 | pub fn get_common_prefix(s1: &String, s2: &String) -> String {| ------- ------- these two types are declared with different lifetimes......5 | std::mem::swap(&mut s1, &mut s2);| ^^^^^^^ ...but data from `s2` flows into `s1` here
I was reading about lifetimes here https://doc.rust-lang.org/rust-by-example/scope/lifetime.html but didn't succeeded
答案1
得分: 12
以下是您要翻译的内容：
如果您尝试显式表达隐式生命周期，您将得到get_common_prefix的以下签名：
fn get_common_prefix<'a, 'b>(s1: &'a String, s2: &'b String) -> String {...}
特别是，您不能交换这两个值，因为两个借用的寿命不会持续相同的时间。相反，您可以这样做
fn get_common_prefix<'a>(s1: &'a String, s2: &'a String) -> String {...}
这样做会解决问题，但也会引发许多其他错误，因为您的代码还有其他问题。让我们一一解决这些问题。
首先，它现在会抱怨std::mem::swap(&mut s1, &mut s2);是非法的，因为
error[E0596]: cannot borrow `s1` as mutable, as it is not declared as mutable--> src/main.rs:4:24|4 | std::mem::swap(&mut s1, &mut s2);| ^^^^^^^ cannot borrow as mutable|help: consider changing this to be mutable|1 | pub fn get_common_prefix<'a>(mut s1: &'a String, s2: &'a String) -> String {| +++error[E0596]: cannot borrow `s2` as mutable, as it is not declared as mutable--> src/main.rs:4:33|4 | std::mem::swap(&mut s1, &mut s2);| ^^^^^^^ cannot borrow as mutable|help: consider changing this to be mutable|1 | pub fn get_common_prefix<'a>(s1: &'a String, mut s2: &'a String) -> String {| +++
但是，Rust非常友好，并告诉您在这种情况下该怎么做，将s1和s2都声明为可变：
fn get_common_prefix<'a>(mut s1: &'a String, mut s2: &'a String) -> String {...}
现在get_common_prefix函数是正确的，但longest_common_prefix中仍然存在错误：
error[E0507]: cannot move out of index of `Vec<String>`--> src/main.rs:16:28|16 | let mut longest_pref = strs[0];| ^^^^^^^ move occurs because value has type `String`, which does not implement the `Copy` trait|help: consider borrowing here|16 | let mut longest_pref = &strs[0];| +
问题是您正在从strs中获取strs[0]，但没有删除它，这是非法的，因为第一个字符串现在被拥有两次（一次由longest_pref拥有，一次由strs拥有）。
一种解决方法是使用swap_remove来实际获取strs[0]（假设我们不关心元素的顺序，它非常高效地从向量中删除元素）：
pub fn longest_common_prefix(mut strs: Vec<String>) -> String {strs.sort();let mut longest_pref = strs.swap_remove(0);for i in 1..strs.len() {longest_pref = get_common_prefix(&longest_pref, &strs[i]);}return longest_pref;}
这样做虽然有效，但效率不高，有几个原因。首先，尽管性能损失不大，但在函数签名中使用&String几乎总是不正确的，因为您可以对其执行的操作（实际上，Rust将为您执行操作，因此您可能不会意识到它）只能将其Deref为&str，这基本上是相同的，但减少了一层间接性（因为您可以将String视为指向str的指针）。因此，我们应该直接编写如下内容：
fn get_common_prefix<'a>(s1: &'a str, s2: &'a str) -> String {...}
此外，在我们可以返回字符串切片（因为我们正在获取子字符串）时，返回String没有意义，因此我们可以直接返回字符串的切片：
pub fn get_common_prefix<'a>(mut s1: &'a str, mut s2: &'a str) -> &'a str {let mut idx: usize = 0;if s1.len() > s2.len() {std::mem::swap(&mut s1, &mut s2);}while idx < s1.len() && s1.chars().nth(idx) == s2.chars().nth(idx) {idx += 1;}return &s1[0..idx]}
请注意，我更改了返回类型和最后一行。
现在，为了使其工作，我们还需要使longest_common_prefix能够使用字符串切片：
pub fn longest_common_prefix(mut strs: Vec<String>) -> String {strs.sort();let mut longest_pref: &str = &strs[0];for i in 1..strs.len() {longest_pref = get_common_prefix(&longest_pref, &strs[i]);}return longest_pref.to_string();}
我们又回到了只是引用strs的第一个元素，而不是获取它。此外，当我们实际需要返回String时，我们只需在一次分配中执行它。
还有其他一些优化要做。首先，对strs进行排序是没有意义的，它不会改变longest_common_prefix的结果，因此我们可以将其删除：
pub fn longest_common_prefix(strs: Vec<String>) -> String {let mut longest_pref: &str = &strs[0];for i in 1..strs.len() {longest_pref = get_common_prefix(&longest_pref, &strs[i]);}return longest_pref.to_string();}
接下来，s1.chars().nth(i)非常慢
英文:
If you tried to explicit the implicit lifetimes, you would get the following signature for get_common_prefix:
fn get_common_prefix<'a, 'b>(s1: &'a String, s2: &'b String) -> String {...}
In particular, you can't swap these two values, because both borrows don't last as long as each other. Instead, you could do
fn get_common_prefix<'a>(s1: &'a String, s2: &'a String) -> String {...}
Doing so will solve the issue, but will also throw a lot of other errors, because there are other issues with your code. Let's go through them one by one.
First of all, it will now complain that std::mem::swap(&mut s1, &mut s2); is illegal because
error[E0596]: cannot borrow `s1` as mutable, as it is not declared as mutable--> src/main.rs:4:24|4 | std::mem::swap(&mut s1, &mut s2);| ^^^^^^^ cannot borrow as mutable|help: consider changing this to be mutable|1 | pub fn get_common_prefix<'a>(mut s1: &'a String, s2: &'a String) -> String {| +++error[E0596]: cannot borrow `s2` as mutable, as it is not declared as mutable--> src/main.rs:4:33|4 | std::mem::swap(&mut s1, &mut s2);| ^^^^^^^ cannot borrow as mutable|help: consider changing this to be mutable|1 | pub fn get_common_prefix<'a>(s1: &'a String, mut s2: &'a String) -> String {| +++
However, Rust is quite nice and tells you what to do in this case, declare both s1 and s2 as mutable:
fn get_common_prefix<'a>(mut s1: &'a String, mut s2: &'a String) -> String {...}
The function get_common_prefix is now correct, but there is still an error in longest_common_prefix:
error[E0507]: cannot move out of index of `Vec<String>`--> src/main.rs:16:28|16 | let mut longest_pref = strs[0];| ^^^^^^^ move occurs because value has type `String`, which does not implement the `Copy` trait|help: consider borrowing here|16 | let mut longest_pref = &strs[0];| +
The problem is that you are taking strs[0] from strs, but not removing it, which is illegal, because the first string would now be owned twice (once by longest_pref, and once by strs).
One solution is to actually take strs[0], with swap_remove (which is very efficient at removing elements from a vector, assuming we don't care about the order of the elements):
pub fn longest_common_prefix(mut strs: Vec<String>) -> String {strs.sort();let mut longest_pref = strs.swap_remove(0);for i in 1..strs.len() {longest_pref = get_common_prefix(&longest_pref, &strs[i]);}return longest_pref;}
This works, but... it's quite inefficient, for several reasons. First of all, even though it's not a terrible performance hit, it's almost always wrong to have a &String in a function signature, because all you can do with it (actually, Rust will do it for you so maybe you don't realize it) is to Deref it to a &str, which is basically the same with one less indirection (because you can see String as a pointer to str). So we should directly write that instead
fn get_common_prefix<'a>(s1: &'a str, s2: &'a str) -> String {...}
Furthermore, there is no point in returning a String, which requires an allocation, when we can just return a slice over that string (because we are taking substrings):
pub fn get_common_prefix<'a>(mut s1: &'a str, mut s2: &'a str) -> &'a str {let mut idx: usize = 0;if s1.len() > s2.len() {std::mem::swap(&mut s1, &mut s2);}while idx < s1.len() && s1.chars().nth(idx) == s2.chars().nth(idx) {idx += 1;}return &s1[0..idx]}
Notice that I changed both the return type and the last line.
Now, for this to work, we also need to adapt longest_common_prefix to work with string slices:
pub fn longest_common_prefix(mut strs: Vec<String>) -> String {strs.sort();let mut longest_pref: &str = &strs[0];for i in 1..strs.len() {longest_pref = get_common_prefix(&longest_pref, &strs[i]);}return longest_pref.to_string();}
We went back to just referencing the first element of strs, not taking it. Also, we perform the allocation into a String just once, when we actually have to return a String.
There are still some other optimizations to be done. First, sorting strs is useless, it won't change the result of the longest_common_prefix, so we can remove that
pub fn longest_common_prefix(strs: Vec<String>) -> String {let mut longest_pref: &str = &strs[0];for i in 1..strs.len() {longest_pref = get_common_prefix(&longest_pref, &strs[i]);}return longest_pref.to_string();}
Next, s1.chars().nth(i) is very slow (Θ(i)). A more efficient way to do this is to reuse the same iterator (s1.chars()), and to advance it at each step, as so
for (c1, c2) in s1.chars().zip(s2.chars()) {if c1 != c2 {break;}idx += 1;}
.zip() will not take any leftover characters from the longest string, so we can actually remove the swap at all, getting
pub fn get_common_prefix<'a>(s1: &'a str, s2: &'a str) -> &'a str {let mut idx: usize = 0;for (c1, c2) in s1.chars().zip(s2.chars()) {if c1 != c2 {break;}idx += c1.len_utf8();}return &s1[0..idx]}
Note: as indicated by @SebastianRedi, idx shouldn't be increased by 1 but by c1.len_utf8(), because when indexing a string, the indexes are expressed in bytes, not in characters, and some characters are more than a single byte long.
答案2
得分: 3
以下是您要翻译的代码部分：
响应评论中的讨论，这是一个正确使用扩展字符簇并适用于字符串切片的任意迭代器的`longest_common_prefix（）`实现：use unicode_segmentation::UnicodeSegmentation;pub fn longest_common_prefix<'a, I>(strings: I) -> &'a strwhereI: IntoIterator<Item = &'a str>,{let mut iters: Vec<_> = strings.into_iter().map(|s| s.graphemes(true)).collect();match iters.len() {0 => return "",1 => return iters[0].as_str(),_ => {}};let first = iters[0].as_str();let mut length = 0;loop {let Some(g) = iters[0].next() else { break; };if iters[1..].iter_mut().any(|iter| iter.next() != Some(g)) {break;}length += g.len();}&first[..length]}在此函数之外仍然需要执行Unicode规范化，例如：use unicode_normalization::UnicodeNormalization;let strings = ...; // 输入字符串let normalized: Vec<String> = strings.iter().map(|s| s.nfc().collect()).collect();let common_prefix = longest_common_prefix(normalized.iter().map(|s| s.as_str()));上述代码使用以下依赖项：unicode-segmentation = "1.10.1"unicode-normalization = "0.1.22"
请注意，我已经将代码部分翻译为中文，不包括代码中的注释。
英文:
In response to the discussion in the comments on the other answer, Here's an implementation of longest_common_prefix() that correctly uses extended grapheme clusters and works for arbitrary iterators of string slices:
use unicode_segmentation::UnicodeSegmentation;pub fn longest_common_prefix<'a, I>(strings: I) -> &'a strwhereI: IntoIterator<Item = &'a str>,{let mut iters: Vec<_> = strings.into_iter().map(|s| s.graphemes(true)).collect();match iters.len() {0 => return "",1 => return iters[0].as_str(),_ => {}};let first = iters[0].as_str();let mut length = 0;loop {let Some(g) = iters[0].next() else { break; };if iters[1..].iter_mut().any(|iter| iter.next() != Some(g)) {break;}length += g.len();}&first[..length]}
Unicode normalization still needs to be performed outside of this function, e.g. like this:
use unicode_normalization::UnicodeNormalization;let strings = ...; // the input stringslet normalized: Vec<String> = strings.iter().map(|s| s.nfc().collect()).collect();let common_prefix = longest_common_prefix(normalized.iter().map(|s| s.as_str()));
The code above uses these dependencies:
unicode-segmentation = "1.10.1"unicode-normalization = "0.1.22"
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论