字符串

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

function letterCombinations(digits: string): string[] {
  const res: string[] = []
  const phoneMap = new Map<string, string>([
    ['2', 'abc'],
    ['3', 'def'],
    ['4', 'ghi'],
    ['5', 'jkl'],
    ['6', 'mno'],
    ['7', 'pqrs'],
    ['8', 'tuv'],
    ['9', 'wxyz'],
  ])

  function backtrack(comb: string, nd: string): void {
    if (!nd.length) res.push(comb)
    else {
      const digit = nd.substring(0, 1)
      const letters = phoneMap.get(digit)!
      for (let i = 0; i < letters.length; i++) {
        const letter = phoneMap.get(digit)!.substring(i, i + 1)
        backtrack(comb + letter, nd.substring(1))
      }
    }
  }

  if (digits.length) backtrack('', digits)
  return res
}

回文子串

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

function countSubstrings(s: string): number {
  const s1 = s.split('').reverse().join('')
  let sum = 0
  const n = s.length

  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j <= n; j++) {
      if (s.substr(i, j - i) === s1.substr(n - j, j - i)) {
        sum+=1
      }
    }
  }

  return sum
}

括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

function generateParenthesis(n: number): string[] {
  const res: string[] = []

  /**
   * @param cur 当前字符串
   * @param left 当前字符串中左括号的数量
   * @param right 当前字符串中右括号的数量
   */
  function recursive(cur: string, left: number, right: number): void {
    if (cur.length === 2 * n) {
      res.push(cur)
      return
    }
    if (left < n) { // 左括号的数量必须小于 n
      recursive(cur + '(', left + 1, right)
    }
    if (right < left) { // 右括号的数量必须小于左括号
      recursive(cur + ')', left, right + 1)
    }
  }

  recursive('', 0, 0)

  return res
}

最长公共前缀

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

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

function longestCommonPrefix(strs: string[]): string {
  if (!strs.length) return ''

  let prefix = strs[0] // 首先令第一个元素为公共前缀
  for (let i = 1; i < strs.length; i++) { // 从第二个元素开始进行遍历
    let j = 0
    for (; prefix.length && j < strs[i].length; j++) {
      if (prefix[j] !== strs[i][j]) { // 让公共前缀和每个元素进行比较，一旦有不同马上退出循环
        break
      }
    }
    prefix = prefix.substr(0, j) // 更新最新公共前缀
    if (prefix === '') return '' // 如果当前公共前缀为空字符串，说明没有公共前缀，无需再遍历，直接退出
  }

  return prefix
}

密码解密

小明从老板那里拿到了一个密码表，需要对密码表进行解密。这个密码表是一个 CSV 文件，里面的数据由数字（没有小数点）、字母组成。小明需要提取每个数据中的数字（例如 1a2b3c 提取后得到 123 ，提取后的数字整体看做一个十进制数），把数值作为奇数的项相加，就可以揭开这个秘密。

function decode(s: string): number {
  return s
    .replace(/[a-zA-Z]/g, '')
    .split('')
    .filter((_, index) => !(index % 2))
    .reduce((pre, cur) => pre + +cur, 0)
}