最长系列

[TOC]

一、3 - 无重复字符的最长子串

1.1 题目

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

示例 1:

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

示例 2:

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

示例 3:

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

1.2 题解

1.2.1 滑动窗口法

• 维护一个滑动窗口，窗口内的都是没有重复的字符，去尽可能的扩大窗口的大小，窗口不停的向右滑动。

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let res = []  // 窗口
    let max = 0 // 最大窗口长度
    for(let item of s) {
      if(res.indexOf(item) !== -1) {
        res.splice(0, res.indexOf(item)+1)  // 窗口左边框左移
      }
      res.push(item)  // 窗口右边框右移
      max = Math.max(max, res.length)
    }
    return max
};

二、5-最长回文字符串

2.1 题目

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

2.2 题解

• 状态：dp[i][j]表示子串s[i][j]是否为回文子串。
• 状态转移方程：dp[i][j] = (s[i] == s[j]) and da[i+1][j-1]
• 边界条件：当j - 1 - ( i + 1) + 1 < 2 时不需要检查子串是否回文
  • 整理，得 j - i < 3 -> j - i + 1 < 4
  • 即，是s[i..j]长度为2或3时，不用检查子串是否回文。
• 初始化：dp[i][i] = true
• 输出：在得到一个状态的值为true的时候，记录起始位置和长度，填完表以后再截取。

三、14-最长公共前缀（longest-common-prefix）

3.1 题目

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。

示例 1:

输入: ["flower","flow","flight"] 输出: "fl" 示例 2:输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。 说明:所有输入只包含小写字母 a-z 。

3.2 题解

• 特殊情况的考虑
  • 字符串数组为空
  • 字符串数组只有一个字符串

3.1 水平扫描法

• 思路
  1. 先找到长度最短的字符串，再从中匹配前缀。
  2. 扫描最短字符串的每一个字符，依次匹配第一个字符是不是公共的，第二个字符是不是公共的...

var longestCommonPrefix = function (strs) {
    
    if (!strs.length) return '';
    if (strs.length === 1) return strs[0];

    let len = strs.length;
    let prefix = strs[0];
    for (let i = 0; i < len - 1; i++) {
        if (strs[i].length > strs[i + 1].length) {
            prefix = strs[i + 1];
        }
    }

    for (let i = 0; i < prefix.length; i++) {
        for (let j = 0; j < len; j++) {
            if (prefix[i] !== strs[j][i]) {
                return prefix.substring(0, i);
            }
        }
    }
    return prefix;
};

• 复杂度分析

  • 时间复杂度：O(S)，S 是所有字符串中字符数量的总和。

    • 最坏情况下，输入数据为 n 个长度为 m 的相同字符串，算法会进行 S = mn 次比较。最好的情况下，算法只需要进行 nstr[0].length次比较，即最长前缀为空时。

  • 空间复杂度：O(1)，我们只需要使用常数级别的额外空间。

2.2 reduce()大法

先找出第一个和第二个的最长前缀，再找出前一个最长前缀与下一个的最长前缀...

var longestCommonPrefix = function (strs) {
    if (!strs.length) return '';
    if (strs.length==1) return strs[0];

    return strs.reduce((prev,next)=>{
        let i = 0;
        while(prev[i]&&next[i]&&prev[i]===next[i]){
            i++;
        }
        return prev.slice(0,i);
    })
};