最长公共前缀

题目

编写一个函数来查找字符串数组中的最长公共前缀. 如果不存在公共前缀, 返回空字符串 "".

提示:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] 仅由小写英文字母组成

示例

输入: strs = ["flower", "flow", "flight"]

输出: "fl"

题解

先假设第一个单词为 prefix, 如果 strs 里所有单词的前缀都是 prefix, 那就返回之; 否则将 prefix 的最后一位删掉继续循环, 直到找出前缀.

JavaScript

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function (strs) {
  strs.sort((a, b) => a.length - b.length)
  let prefix = strs[0]
  let flag = false

  while (!flag) {
    flag = strs.every((str) => str.startsWith(prefix))

    if (!flag) {
      prefix = prefix.slice(0, -1)
    }
  }

  return prefix
}

Rust

pub fn longest_common_prefix(strs: Vec<String>) -> String {
    let mut strs = strs;
    strs.sort();
    let mut prefix: &str = &strs[0];
    let mut has_found = false;

    while !has_found {
        has_found = strs.iter().all(|str| str.starts_with(prefix));

        if !has_found {
            prefix = &prefix[0..prefix.len() - 1];
        }
    }

    prefix.to_string()
}