[閒聊] 每日leetcode 75 - Day2

[yam276 (史萊哲林的優等生)]

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

在 --release 等於無開銷


例子：

trait Pipe: Sized {
    fn pipe<F, T>(self, f: F) -> T
    where
        F: FnOnce(Self) -> T,
    {
        f(self)
    }
}

impl<T> Pipe for T {}

fn main() {
    let result = 10.pipe(|x| x * 2);
    println!("{}", result); // 20
}

在 --release 會等價於：

fn main() {
    let result = 10 * 2;
    println!("{}", result); // 20
}


第二版 Code:

trait Pipe: Sized {
    fn pipe<F, T>(self, f: F) -> T
    where
        F: FnOnce(Self) -> T,
    {
        f(self)
    }
}

impl<T> Pipe for T {}

impl Solution {
    pub fn gcd_of_strings(str1: String, str2: String) -> String {
        Self::gcd(str1.len(), str2.len()).pipe(|gcd_len| {
            str1[..gcd_len].to_string().pipe(|x| {
                if x.repeat(str1.len() / gcd_len) == str1 &&
                   x.repeat(str2.len() / gcd_len) == str2 {
                    x
                } else {
                    "".to_string()
                }
            })
        })
    }

    fn gcd(mut a: usize, mut b: usize) -> usize {
        while b != 0 {
            a %= b;
            std::mem::swap(&mut a, &mut b);
        }
        a
    }
}


看了一下消耗 memory 跟第一版一樣

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.248.143.163 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1748419917.A.D6C.html
推 oin1104: 大師
※ 編輯: yam276 (60.248.143.163 臺灣), 05/28/2025 16:14:02
推 DJYOMIYAHINA: 大師