最长公共前缀

题目

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

提示:

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

示例

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

输出: "fl"

题解

先按长度从小到大排序, 因为 lcp 最长也就是整个数组中最短的那个单词, 然后令其为初始的 lcp, 如果 strs 里所有单词的前缀都是 lcp, 那就返回之; 否则将 lcp 的最后一位删掉继续循环, 直到找出前缀.

JavaScript

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

  while (true) {
    if (strs.every((str) => str.startsWith(lcp))) {
      break
    } else {
      lcp = lcp.slice(0, -1)
    }
  }

  return lcp
}

Rust

pub fn longest_common_prefix(strs: Vec<String>) -> String {
    let mut strs = strs;
    strs.sort();

    let mut prefix: &str = &strs[0];

    loop {
        if strs.iter().all(|str| str.starts_with(prefix)) {
            break;
        } else {
            prefix = &prefix[0..prefix.len() - 1];
        }
    }

    prefix.to_string()
}