最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"

示例 2：

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

提示：

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

暴力枚举

TypeScript

function longestCommonPrefix(strs: string[]): string {
    if (!strs.length) return "";
    if (strs.length === 1) return strs[0];
    for (let i = 0; i < strs[0].length; i++) {
        for (let j = 0; j < strs.length; j++) {
            if (strs[0][i] !== strs[j][i]) {
                return strs[0].slice(0, i);
            }
        }
    }
    return strs[0];
};

二分查找法

TypeScript

function longestCommonPrefix(strs: string[]): string {
  if (strs.length === 0) {
    return "";
  }
  let minLen = Number.MAX_SAFE_INTEGER;
  for (const str of strs) {
    minLen = Math.min(minLen, str.length);
  }
  let low = 0;
  let high = minLen;
  while (low < high) {
    const mid = Math.floor((low + high + 1) / 2);
    if (isCommonPrefix(strs, mid)) {
      low = mid;
    } else {
      high = mid - 1;
    }
  }
  return strs[0].substring(0, low);
}

function isCommonPrefix(strs: string[], len: number): boolean {
  const prefix = strs[0].substring(0, len);
  for (let i = 1; i < strs.length; i++) {
    if (!strs[i].startsWith(prefix)) {
      return false;
    }
  }
  return true;
}

字典

TypeScript

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEndOfWord: boolean = false;
}

class Trie {
  root: TrieNode = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (let i = 0; i < word.length; i++) {
      const c = word.charAt(i);
      if (!node.children.has(c)) {
        node.children.set(c, new TrieNode());
      }
      node = node.children.get(c)!;
    }
    node.isEndOfWord = true;
  }

  searchPrefix(prefix: string): TrieNode | null {
    let node = this.root;
    for (let i = 0; i < prefix.length; i++) {
      const c = prefix.charAt(i);
      if (!node.children.has(c)) {
        return null;
      }
      node = node.children.get(c)!;
    }
    return node;
  }
}

function longestCommonPrefix(strs: string[]): string {
  if (strs.length === 0) {
    return "";
  }
  const trie = new Trie();
  for (const str of strs) {
    trie.insert(str);
  }
  let node = trie.root;
  let prefix = "";
  while (node.children.size === 1 && !node.isEndOfWord) {
    const nextChar = node.children.keys().next().value;
    prefix += nextChar;
    node = node.children.get(nextChar)!;
  }
  return prefix;
}

最长公共前缀 ​

暴力枚举 ​

二分查找法 ​

字典 ​

最长公共前缀

暴力枚举

二分查找法

字典