14.最长公共前缀

链接：14.最长公共前缀
难度：Easy
标签：字典树、字符串
简介：编写一个函数来查找字符串数组中的最长公共前缀。

题解 1 - typescript

• 编辑时间：2020-06-03
• 执行用时：80ms
• 内存消耗：36.4MB
• 编程语言：typescript
• 解法介绍：内部用函数判断头部重复字符数。

function longestCommonPrefix(strs: string[]): string {
  const len = strs.length;
  if (len === 0) return '';
  let commonS = strs[0];
  for (let i = 1; i < len; i++) if ((commonS = comp(strs[i], commonS)) === '') return commonS;
  return commonS;
  function comp(s: string, commonS: string): string {
    for (let i = 0, minLen = Math.min(s.length, commonS.length); i <= minLen; i++)
      if (s[i] !== commonS[i]) return commonS.substring(0, i);
    return commonS;
  }
}

题解 2 - typescript

• 编辑时间：2020-06-15
• 执行用时：84ms
• 内存消耗：37MB
• 编程语言：typescript
• 解法介绍：纵向判断。

function longestCommonPrefix(strs: string[]): string {
  const len = strs.length;
  if (len === 0) return '';
  const commonPrefix = strs[0];
  for (let i = 0, cl = commonPrefix.length; i < cl; i++)
    for (const str of strs) if (commonPrefix[i] !== str[i]) return commonPrefix.substring(0, i);
  return commonPrefix;
}

题解 3 - cpp

• 编辑时间：2021-12-20
• 执行用时：4ms
• 内存消耗：9MB
• 编程语言：cpp
• 解法介绍：遍历每一位。

class Solution {
   public:
    string longestCommonPrefix(vector<string>& strs) {
        int n = strs.size();
        int maxn = 200;
        for (int i = 0; i < n; i++) {
            if (strs[i].size() < maxn) maxn = strs[i].size();
        }
        string ans = "";
        if (maxn == 0) return ans;
        for (int i = 0; i < maxn; i++) {
            char ch = strs[0][i];
            for (int j = 1; j < n; j++) {
                if (strs[j][i] != ch) return ans;
            }
            ans += ch;
        }
        return ans;
    }
};

题解 4 - typescript

• 编辑时间：2021-10-16
• 执行用时：80ms
• 内存消耗：40.4MB
• 编程语言：typescript
• 解法介绍：字典树。

class TrieNode {
  end = false;
  children: Map<string, TrieNode> = new Map();
  constructor(public val: string) {}
}
class Trie {
  private _size = 0;
  get size() {
    return this._size;
  }
  get empty() {
    return this._size === 0;
  }
  private _root = new TrieNode('');
  get root() {
    return this._root;
  }
  clear() {
    this._root = new TrieNode('');
    this._size = 0;
  }
  add(str: string) {
    return this._add(str);
  }
  private _add(str: string, node = this._root) {
    if (str.length === 0) {
      this._root.end = true;
      this._size++;
      return;
    }
    if (str.length === 1) {
      let endNode = node.children.get(str);
      if (!endNode) node.children.set(str, (endNode = new TrieNode(str)));
      if (!endNode.end) {
        endNode.end = true;
        this._size++;
      }
      return;
    }
    const first = str[0];
    let nextNode = node.children.get(first);
    if (!nextNode) node.children.set(first, (nextNode = new TrieNode(first)));
    const nextStr = str.substr(1);
    this._add(nextStr, nextNode);
  }
  contains(str: string) {
    const endNode = this.findEndNode(str);
    return endNode ? endNode.end : false;
  }
  remove(str: string) {
    const endNode = this.findEndNode(str);
    if (endNode && endNode.end) {
      endNode.end = false;
      this._size--;
    }
  }
  starsWith(str: string) {
    return this.findEndNode(str) !== null;
  }
  private findEndNode(str: string, node = this._root): TrieNode | null {
    if (str.length === 0) return this._root;
    if (str.length === 1) return node.children.get(str) ?? null;
    const first = str[0];
    let nextNode = node.children.get(first);
    if (!nextNode) return null;
    const nextStr = str.substr(1);
    return this.findEndNode(nextStr, nextNode);
  }
}
function longestCommonPrefix(strs: string[]): string {
  const trie = new Trie();
  for (const str of strs) {
    if (str === '') return '';
    trie.add(str);
  }
  let node = trie.root;
  let ans = '';
  while (node.children.size === 1 && !node.end) {
    ans += node.val;
    node = [...node.children.values()][0];
  }
  ans += node.val;
  return ans;
}