leetcode_rust/problems_cn/p000_0xx/
p000_014.rs

1//! # 问题描述
2//!
3//! 编写一个函数来查找字符串数组中的最长公共前缀。
4//! 
5//! 如果不存在公共前缀,返回空字符串 `""`。
6//! 
7//! 示例 1:
8//! 
9//! ```plain
10//! 输入:strs = ["flower","flow","flight"]
11//! 输出:"fl"
12//! ```
13//! 
14//! 示例 2:
15//! 
16//! ```plain
17//! 输入:strs = ["dog","racecar","car"]
18//! 输出:""
19//! 解释:输入不存在公共前缀。
20//! ```
21//! 
22//! 提示:
23//! 
24//! - `1 $\leqslant$ strs.length $\leqslant$ 200`
25//! - `0 $\leqslant$ strs[i].length $\leqslant$ 200`
26//! - `strs[i]` 仅由小写英文字母组成
27//! 
28//! 来源:<https://leetcode.cn/problems/longest-common-prefix/>
29
30////////////////////////////////////////////////////////////////////////////////
31
32/// 最长公共前缀
33///
34/// # 参数
35/// * `strs` - 输入字符串
36pub fn longest_common_prefix(strs: Vec<String>) -> String {
37    let mut prefix: Vec<u8> = vec![];
38
39    for idx_0 in 0..strs[0].len() {
40        let ch = strs[0].as_bytes()[idx_0];
41        for idx_n in 1..strs.len() {
42            if strs[idx_n].len() == idx_0 || ch != strs[idx_n].as_bytes()[idx_0] {
43                // Early exit
44                return String::from_utf8(prefix).unwrap();
45            }
46        }
47        prefix.push(ch);
48    }
49
50    String::from_utf8(prefix).unwrap()
51}
52
53#[cfg(test)]
54mod tests {
55    use super::longest_common_prefix;
56
57    #[test]
58    fn test_longest_common_prefix() {
59        let res = longest_common_prefix(
60            vec!["abcd", "a", ""]
61                .iter()
62                .map(|s| s.to_string())
63                .collect::<Vec<String>>(),
64        );
65        assert_eq!(res, "");
66        
67        let res = longest_common_prefix(
68            vec!["abcd", "a", "adc"]
69                .iter()
70                .map(|s| s.to_string())
71                .collect::<Vec<String>>(),
72        );
73        assert_eq!(res, "a");
74    }
75}