最长公共前缀

发表于 | 阅读次数: |

题目
编写一个函数来查找字符串数组中的最长公共前缀；如果不存在公共前缀，则返回 ""。注意：所有输入只包含小写字母 a-z

示例1

1
2
输入：["flower", "flow", "flight"]
输出："fl"

示例2

1
2
输入：["dog", "rececar", "car"]
输出：""

解题思路
首先将输入的数组中第一个取出作为最长公共前缀，依次截取处理；如果公共前缀和后面的所有值都都能匹配部分且匹配位置从0开始，即该截取的字符是所有数组中的值的公共前缀。

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function longestCommonPrefix(arrData) {
  const maxCommonPrefix = arrData[0];
  let maxCommonPrefixIndex = -1;

  if (!arrData.length) return "";

  if (arrData.length === 1) return maxCommonPrefix;

  for (let i = 0; i < maxCommonPrefix.length; i++) {
    const curCommonStr = maxCommonPrefix.substring(0, i + 1);
    let isCommonFlag = true;

    for (let j = 1; j < arrData.length; j++) {
      const curCommonIndexOfNum = arrData[j].indexOf(curCommonStr);

      if (curCommonIndexOfNum !== 0) {
        isCommonFlag = false;
        break;
      }
    }

    if (isCommonFlag) maxCommonPrefixIndex = i;
  }

  return maxCommonPrefixIndex > -1 ? maxCommonPrefix.substring(0, maxCommonPrefixIndex + 1) : "";
}

总结
公共前缀：数组的所有子项值都要从字符串第一位开始，且子项中都满足包含同一个子串信息，那么这个子串就是公共前缀。
在查找公共前缀的过程中，将数组的第一个值的截取直接当做了公共前缀并和其他数组值进行了比较，存储最终的公共前缀的位置信息；当比较完之后将位置信息返回并截取数组第一个字符串的值返回即可。