leetcode_rust/problems/p000_0xx/
p000_014.rs

1//! # Description
2//!
3//! Write a function to find the longest common prefix string amongst an array of strings.
4//!
5//! If there is no common prefix, return an empty string `""`.
6//!
7//! Example 1:
8//!
9//! ```plain
10//! Input: strs = ["flower","flow","flight"]
11//! Output: "fl"
12//! ```
13//!
14//! Example 2:
15//!
16//! ```plain
17//! Input: strs = ["dog","racecar","car"]
18//! Output: ""
19//! Explanation: There is no common prefix among the input strings.
20//! ```
21//! 
22//! Constraints:
23//!
24//! - `1 $\leqslant$ strs.length $\leqslant$ 200`
25//! - `0 $\leqslant$ strs[i].length $\leqslant$ 200`
26//! - `strs[i]` consists of only lowercase English letters.
27//!
28//! Sources: <https://leetcode.com/problems/longest-common-prefix/>
29
30////////////////////////////////////////////////////////////////////////////////
31
32/// Longest Common Prefix
33///
34/// # Arguments
35/// * `strs` - input strings
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}
leetcode_rust/problems/p000_0xx/p000_014.rs

leetcode_rust/problems/p000_0xx/
p000_014.rs
