14. Longest Common Prefix Easy

1/**
2 * [14] Longest Common Prefix
3 *
4 * Write a function to find the longest common prefix string amongst an array of strings.
5 * If there is no common prefix, return an empty string "".
6 *  
7 * Example 1:
8 *
9 * Input: strs = ["flower","flow","flight"]
10 * Output: "fl"
11 *
12 * Example 2:
13 *
14 * Input: strs = ["dog","racecar","car"]
15 * Output: ""
16 * Explanation: There is no common prefix among the input strings.
17 *
18 *  
19 * Constraints:
20 *
21 * 1 <= strs.length <= 200
22 * 0 <= strs[i].length <= 200
23 * strs[i] consists of only lower-case English letters.
24 *
25 */
26pub struct Solution {}
27
28// problem: https://leetcode.com/problems/longest-common-prefix/
29// discuss: https://leetcode.com/problems/longest-common-prefix/discuss/?currentPage=1&orderBy=most_votes&query=
30
31// submission codes start here
32
33impl Solution {
34    pub fn longest_common_prefix(strs: Vec<String>) -> String {
35        if strs.len() == 1 {
36            return strs[0].clone();
37        }
38        let mut i = 0;
39        loop {
40            for j in 1..strs.len() {
41                if i >= strs[j].len()
42                    || i >= strs[j - 1].len()
43                    || strs[j][i..i + 1] != strs[j - 1][i..i + 1]
44                {
45                    return strs[j][0..i].to_owned();
46                }
47            }
48            i += 1;
49        }
50    }
51}
52
53// submission codes end
54
55#[cfg(test)]
56mod tests {
57    use super::*;
58
59    #[test]
60    fn test_14() {
61        assert_eq!(
62            Solution::longest_common_prefix(vec![
63                "dog".to_owned(),
64                "racecar".to_owned(),
65                "car".to_owned()
66            ]),
67            ""
68        );
69        assert_eq!(
70            Solution::longest_common_prefix(vec![
71                "flower".to_owned(),
72                "flow".to_owned(),
73                "flight".to_owned()
74            ]),
75            "fl"
76        );
77        assert_eq!(
78            Solution::longest_common_prefix(vec!["car".to_owned(), "carpet".to_owned(),]),
79            "car"
80        );
81        assert_eq!(
82            Solution::longest_common_prefix(vec!["".to_owned(), "carpet".to_owned(),]),
83            ""
84        );
85        assert_eq!(
86            Solution::longest_common_prefix(vec!["carpet".to_owned(),]),
87            "carpet"
88        );
89    }
90}
91