1071. Greatest Common Divisor of Strings
https://leetcode.com/problems/greatest-common-divisor-of-strings/
题意：
两个输入字串 找最大公因子子字串
让他们都可以被子字串的重复字串组成
思路：
本来想说从 0..str1 开始找
但暴力解效率太低了
后面想到算最大公因子
因为两个字串都是重复要素组成
只要这个最大公因子长度的子字串可以组成他们 就是答案
不能就回空字串 代表解不存在
另外我叫 AI 随便给我一个高效率 gcd 的函数
不想用 crate
第一版 Code:
impl Solution {
pub fn gcd_of_strings(str1: String, str2: String) -> String {
let gcd_len = Self::gcd(str1.len(), str2.len());
let x = &str1[..gcd_len];
let res =
(str1 == x.repeat(str1.len() / gcd_len)) &&
(str2 == x.repeat(str2.len() / gcd_len));
if res {
return x.to_string();
}
"".to_string()
}
pub fn gcd(mut a: usize, mut b: usize) -> usize {
while b != 0 {
a %= b;
std::mem::swap(&mut a, &mut b);
}
a
}
}
我在思考能不能弄成一行
找到可以用 pipe 方法
pipe 代表前面的计算结果放进后面继续处理
Rust 的 pipe 功能还在 nightly 是 unstable 的
但可以用泛型自己实作
这是 AI 帮我写的：
trait Pipe: Sized {
fn pipe<F, T>(self, f: F) -> T
where
F: FnOnce(Self) -> T,
{
f(self)
}
}
impl<T> Pipe for T {}
我还查了一下会不会有额外开销
答案是 Rust 编译器很聪明
会把这种简单小函数做 inline 优化处理
在

大师

大师