leetcode字符串习题

2020-01-25 by 杜宏伟

字符串很常见,熟悉字符串的操作很有意义。

无重复字符的最长子串

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

滑动窗口 + 哈希表。一个窗口内发现有重复数后,可以直接完全跳过这个窗口,直接到下一个窗口。

时间复杂度:O(n)O(n),索引 jj 将会迭代 nn 次。

空间复杂度(HashMap):O(min(m, n))O(min(m,n))

空间复杂度(Table):O(m)O(m),mm 是字符集的大小。

电话号码的字母组合

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

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

示例:

输入:"23"
输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

递归。本题是递归最简单的情况,没有条件,没有重复。

最小规模的情况是,一且字符,与另一组字符的两两组合。比如 ["a", "b", "c"]与["d", "e", "f"]两两组合。如果是三组,就是1组与2,3组的结果两峡两组合。

从生成结果的角度来看,有两种思路,从左到右的生成结果或从右到左生成结果。较通用的做法是从左向右生成结果。

先声明一个map

const map = {
  2: ["a", "b", "c"],
  3: ["d", "e", "f"],
  4: ["g", "h", "i"],
  5: ["j", "k", "l"],
  6: ["m", "n", "o"],
  7: ["p", "q", "r", "s"],
  8: ["t", "u", "v"],
  9: ["w", "x", "y", "z"]
};

先来看从左到右的思路 部分答案 + 当前可以字符 ,直接到后一层,会一起得到完整答案。

function letterCombinations(digits) {
  let result = []
  function helper(digits, item) {
    if (digits == '') {
      result.push(item)
      return
    }
    let digitItem = map[digits[0]]
    for (let c of digitItem) {
      helper(digits.substr(1), item + c)
    }
  }
  if (digits == '') {
    return []
  }
  else {
    helper(digits, '')
    return result
  }
}

每次递归只取出一个字符,导致每取一个字符就会生成一个递归函数,生成的函数总数会比较多

下面看一下从右到左的想法


function letterCombinations(digits) {
  if (digits.length == 0) {
    return []
  }
  if (digits.length == 1) {
    return map[digits]
  }
  let result = []
  let letters = map[digits[0]]
  let subResult = letterCombinations(digits.substr(1))
  for (let c of letters) {
    for (let item of subResult) {
      result.push(c + item)
    }
  }
  return result
}

没有内嵌函数,代码比较漂亮,思想也好描述:当前问题可以分解成 当前可选字符 + 后面成生的字符串,可惜不是每个问题都可以这样写,因为下一层的状态可能在这一层决定不了。

这种做好,感觉就是动态规划的思路,从问题的最小规模求解,记录每个规模下的每个答案。后面的答案需要用到前面的结果。只是写法用了递归的写法而已。

下面是动态规划的写法,思想是一样的。

function letterCombinations(digits) {
  if(digits=='') return []
  let dp = [map[digits[0]]]
  let tmp = []
  for (let i = 1; i < digits.length; i++) {
    let arr = map[digits[i]]
    for (let m = 0; m < arr.length; m++) {
      for (let n = 0; n < dp[i - 1].length; n++) {
        tmp.push(`${dp[i - 1][n]}${arr[m]}`)
      }
    }
    dp[i] = tmp
    tmp = []
  }
  return dp[dp.length-1]
}

可能你觉得这不是动态规划。其实算法之间没什么分别,只是人们为了记得方便,起了个名字而已。但思想是没有界限的。不要因为递归,动态规划这些名字束缚了思想。

上面的算法可以优化一下,因为并不需要保存每一层,只需要保证上一层的结果即可。

function letterCombinations(digits) {
  if (digits == '') return []
  let dp = [map[digits[0]], []]
  for (let i = 1; i < digits.length; i++) {
    let arr = map[digits[i]]
    for (let m = 0; m < arr.length; m++) {
      for (let n = 0; n < dp[0].length; n++) {
        dp[1].push(`${dp[0][n]}${arr[m]}`)
      }
    }
    dp = [dp[1], []]
  }
  return dp[0]
}

括号生成

给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。

例如,给出 n = 3,生成结果为:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

容易想到的就是递归 + 剪枝

var generateParenthesis = function (n) {
  let result = []
  helper(n, n, '')

  function helper(left, right, item) {
    //括号没有了,当然就是一个解了
    if (left == 0 && right == 0) {
      result.push(item)
      return
    }
    //左括号是不限量的,只要有,就可以取
    if (left > 0) {
      helper(left - 1, right, item + '(')
    }
    //右括号是限量的,只有已经取过左括号,才能取右括号
    if (right > left) {
      helper(left, right - 1, item + ')')
    }

  }
  return result
};

本题也可以用动态规划,不过不大容易想出来,也不好维护,就不举例了。

实现 strStr()

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。

双指针法。

需要注意的是,如果needle为空,返回 0

串联所有单词的子串

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配,中间不能有其他字符,但不需要考虑 words 中单词串联的顺序。

示例 1:

输入:
  s = "barfoothefoobarman",
  words = ["foo","bar"]
输出:[0,9]
解释:
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2:

输入:
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
输出:[]
  1. 暴力法。对words做一个全组合形成可能的所有字符串 str,然后 s.indexOf(str)可得解
  2. 动态规划。我们注意到长度相同,这就为城市规划提供的前题。在例1中,记录s中长度为3的子串是否匹配单词,再以长度3为基础,判断长度6的子串是否为答案。注意的是每3个匹配的都是不一样的单词,所以在记录的时候需要记录单词的编号。

最长有效括号

给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。

用栈。遇到)就弹出,直到(,记录startIndex,endIndex

  1. 如果没有匹配的 ) 就一直弹到底,这段子串无解。
  2. 分析所有的startIndex,endIndex,得到最长有限长度。

字母异位词分组

给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

排序 + hash

我叫杜宏伟,前端开发。

一直想写博客,在2018的年的最后几天,终于上线了。

对于前端开发,一个特点就是太零散,很容易会了后面忘了前面,所以归纳总结很重要。再有就是分享,做前端好多年,以前都是看你们写的文章, 现在我也开始写一些,希望可以帮到入行的小伙伴。微信号 duhongwei5775

欢迎转载,只需注明作者,出处即可

版权说明:署名 4.0 国际(CC BY 4.0)