Longest substring from a vector of strings in rust

longest_substring.rs

/*
Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.


*/

pub fn longest_common_prefix(strs: Vec<String>) -> String {
  // empty vector input case
  if strs.len() == 0 {
    return String::new();
  } else if strs.len() == 1 {
    // only one String in vector
    return strs[0].clone();
  }

  // Pick an arbitrary word, I chose the first word
  let base = &strs[0];

  // declare tracking vars to walk through the vector and track best match
  let mut sub_string = String::new();
  let mut best_match = String::new();

  for char in base.chars() {
    // grow the sub_string one character at a time
    sub_string.push(char);

    // look for the sub_string in all the other words, skipping the first word
    for word in &strs[1..] {
      if word.contains(&sub_string) {
        // if you find the substring in the word
        // if substring is longer than current best match
        if sub_string.len() > best_match.len() {
          // update best match
          best_match = String::from(&sub_string);
        }
      } else {
        // found a substring that is not in all the words
        if sub_string.len() == best_match.len() && sub_string.contains(&best_match) {
          best_match.pop();
        }
        // clear out the substring
        sub_string.clear();
        break;
      }
    }
  }
  // return the best found substring
  best_match
}

#[cfg(test)]
mod test {
  use super::*;

  #[test]
  fn can_convert_1() {
    let input = vec![
      String::from("flower"),
      String::from("flow"),
      String::from("flight"),
    ];
    let expected = String::from("fl");
    assert_eq!(expected, longest_common_prefix(input));
  }

  #[test]
  fn can_convert_2() {
    let input = vec![
      String::from("dog"),
      String::from("car"),
      String::from("racecar"),
    ];
    let expected = String::from("");
    assert_eq!(expected, longest_common_prefix(input));
  }
  #[test]
  fn can_convert_3() {
    let input = vec![String::from("a")];
    let expected = String::from("a");
    assert_eq!(expected, longest_common_prefix(input));
  }

  #[test]
  fn can_convert_4() {
    let input = vec![];
    let expected = String::new();
    assert_eq!(expected, longest_common_prefix(input));
  }

  #[test]
  fn can_convert_5() {
    let input = vec![String::from("a"), String::from("a")];
    let expected = String::from("a");
    assert_eq!(expected, longest_common_prefix(input));
  }
}