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 優化處理
在

大師

大師