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}