字符串解析与校验

如何验证一个 IP 地址字符串？

• 先按 . 切分: 得到 4 段则可能是 IPv4;
  • 每段必须是纯数字;
  • 数值范围 0 ~ 255;
  • 不允许前导零, 即 "0" 只能单独成为一段;
• 再按 : 切分: 得到 8 段则可能是 IPv6;
  • 每段长度为 1 ~ 4;
  • 只允许十六进制字符 [0-9a-fA-F];
  • 允许前导零;
• 两者都不满足: 返回 "Neither";

function validIPAddress(queryIP: string): string {
  const v4 = queryIP.split(".");
  if (v4.length === 4) {
    for (const part of v4) {
      if (!/^\d+$/.test(part)) return "Neither";
      const num = Number(part);
      if (num < 0 || num > 255) return "Neither";
      if (part[0] === "0" && part.length !== 1) return "Neither";
    }
    return "IPv4";
  }

  const v6 = queryIP.split(":");
  if (v6.length === 8) {
    for (const part of v6) {
      if (!/^[a-fA-F0-9]{1,4}$/.test(part)) return "Neither";
    }
    return "IPv6";
  }

  return "Neither";
}

如何比较版本号？

• 切分: 按 . 拆成数字段;
• 对齐: 两段数不同时, 缺失段按 0 处理;
• 比较: 从左到右逐段比较, 首个不相等的段决定大小;
• 返回: 前者大返回 1, 前者小返回 -1, 全部相等返回 0;

function compareVersion(version1: string, version2: string): number {
  const v1 = version1.split(".").map(Number);
  const v2 = version2.split(".").map(Number);
  const len = Math.max(v1.length, v2.length);

  for (let i = 0; i < len; i++) {
    const a = v1[i] ?? 0;
    const b = v2[i] ?? 0;
    if (a > b) return 1;
    if (a < b) return -1;
  }
  return 0;
}

如何求一组字符串的最长公共前缀？

• 思路: 按列比较, 固定第 i 列逐个字符串比较同一位置的字符;
• 终止: 某列出现不同字符时, 答案就是第一个字符串的前 i 个字符;
• 兜底: 所有列都相同则返回第一个字符串本身;
• 复杂度: 时间 O(m × n), m 为最短串长度, n 为字符串个数; 空间 O(1);

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