最长回文子串

最长回文子串LeetCode5
题目：给你一个字符串 s，找到 s 中最长的回文子串。
输入：s = “babad” 输出：”bab” 解释：”aba” 同样是符合题意的答案。
输入：s = “cbbd” 输出：”bb”

方法一：使用暴力遍历，枚举每一个组合字符串，判断该是否是回文，时间复杂度较高O(n3)，空间复杂度O(1)

  1. // 判断字符串是否是回文
  2. const isReverse = function (str, left, right) {
  3.   let start = left;
  4.   let end = right;
  5.   while (start < end) {
  6.     if (str[start] === str[end]) {
  7.       start++;
  8.       end--;
  9.     } else {
  10.       return false;
  11.     }
  12.   }
  13.   return true;
  14. }
  16. var longestPalindrome = function(s) {
  17.   // 最长回文字符串开始索引
  18.   let start = 0;
  19.   // 最长回文字符串长度
  20.   let len = 1;
  21.   for (let i = 0; i < s.length; i++) {
  22.     for (let j = i + 1; j < s.length; j++) {
  23.       if (isReverse(s, i, j) && j - i + 1 > len) {
  24.         start = i;
  25.         len = j - i + 1;
  26.       } 
  27.     }
  28.   }
  29.   return s.substr(start, len);
  30. };

方法二：使用中心扩散法，以一个元素为中心向两边扩散，判断扩散后的字符串是否为回文，如果是，继续扩散，如果不是，返回当前回文长度
每一个元素扩散时会有两种场景，奇数回文和偶数回文，奇数回文就是回文字符串是奇数，中心元素两边的字符串是对称的，偶数回文就回文字符串是偶数，两两对称，比较这两种场景下回文字符串的长度，即可获得以当前元素为中心的最长回文子串

  1. // 获取回文子串的长度
  2. const getMaxReverseStr = function (str, left, right) {
  3.   let start = left;
  4.   let end = right;
  5.   while (start >= 0 && end < str.length && str[start] === str[end]) {
  6.     start--
  7.     end++;
  8.   }
  9.   // end和start不相等时需要各自还原end - 1 - (start + 1) + 1
  10.   return end - start - 1;
  11. }
  13. var longestPalindrome = function(s) {
  14.   let start = 0;
  15.   let len = 1;
  16.   for (let i = 0; i < s.length; i++) {
  17.     const evenReverseLen = getMaxReverseStr(s, i, i + 1);
  18.     const oddReverseLen = getMaxReverseStr(s, i, i);
  19.     const curLen = Math.max(evenReverseLen, oddReverseLen);
  20.     if (len < curLen) {
  21.       len = curLen;
  22.       // 将长度转换成索引需要减一
  23.       start = i - Math.floor((curLen - 1) / 2);
  24.     }
  25.   }
  26.   return s.substr(start, len);
  27. };

方法三：动态规划
按照数学角度，i，j分别表示第i个和第j个字符，如果s[i] === s[j] 且字符串[i + 1][j-1]是回文串，那么字符串[i][j]就一定是回文串，将字符串[i + 1][j-1]是否是回文串的结果存储起来，即可知道[i][j]是否为回文，
定义result[i][j]表示字符串从i到j是否是回文子串，且每一个单独的字符都是回文串，所以result[i][i]=1
当s[i] === s[j]时，有两种场景

  • 当i + 1< j - 1，即j - i > 2，result[i][j]是否是回文依赖result[i + 1][j-1]
  • 当两个元素相邻且相等，或两个元素隔着一个元素且相等，即j = i + 1 || i + 1 === j - 1 时，即j - i <= 2，则result[i][j]=1

注意：外层需要从j开始循环，如果外层从i开始循环，对result[i+1][j-1]取值时，还不知道result[i+1][j-1]是否是回文串

  1. var longestPalindrome = function (s) {
  2.   const length = s.length;
  3.   let start = 0;
  4.   let len= 1;
  5.   const result = (new Array(length)).fill().map((_, i) => (new Array(length)).fill(0).map((_, j) => i === j ? 1 : 0));
  7.   for (let j = 1; j < length; j++) {
  8.     for (let i = 0; i < j; i++){
  9.       if (s[i] === s[j]) {
  10.         if (j - i <= 2) {
  11.           result[i][j] = 1;
  12.         } else {
  13.           result[i][j] = result[i + 1][j - 1];
  14.         }
  15.         if (result[i][j] && len < j - i + 1) {
  16.           start = i;
  17.           len = j - i + 1;
  18.         }
  19.       }
  20.     }
  21.   }
  22.   return s.substr(start, len);
  23. };

空间复杂度为O(n2)，观察代码发现，每次拿存储结果的时候只需要第i+1行、第j-1列的结果，对于j-2列、j-3列的结果其实不需要存储，每次使用一个数组，进行覆盖即可，优化后空间复杂度降低，但是代码可读性变差，需要耗费时间去理解这么写的意义

  1. var longestPalindrome = function (s) {
  2.   const length = s.length;
  3.   let start = 0;
  4.   let len= 1;
  5.   const result = new Array(length).fill(0);
  7.   for (let j = 1; j < length; j++) {
  8.     for (let i = 0; i < j; i++){
  9.       if (s[i] === s[j]) {
  10.         if (j - i <= 2) {
  11.           result[i] = 1;
  12.         } else {
  13.           result[i] = result[i + 1];
  14.         }
  15.         if (result[i] && len < j - i + 1) {
  16.           start = i;
  17.           len = j - i + 1;
  18.         }
  19.       } else {
  20.         // 当前列不相等时进行清零
  21.         result[i] = 0;
  22.       }
  23.     }
  24.   }
  25.   return s.substr(start, len);
  26. };

无重复字符的最长子串

无重复字符的最长子串LeetCode3
题目：给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
输入: s = “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
输入: s = “bbbbb” 输出: 1
输入: s = “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

方法一：使用暴力解法，遍历每个子串，判断下一个字符在子串中是否重复

  1. const isContain = function (s, left, right, target) {
  2.   let start = left;
  3.   while (start <= right) {
  4.     if (s[start] === target) {
  5.       return true;
  6.     }
  7.     start++;
  8.   }
  9.   return false;
  10. }
  12. var lengthOfLongestSubstring = function(s) {
  13.   const length = s.length;
  14.   if (length === 0) return 0;
  15.   let len = 1;
  16.   for (let i = 0; i < length; i++) {
  17.     for (let j = i + 1; j < length; j++) {
  18.       if (isContain(s, i, j - 1, s[j])) {
  19.         break;
  20.       }
  21.       if (len < j - i + 1) {
  22.         len = j - i + 1;
  23.       }
  24.     }
  25.   }
  26.   return len;
  27. };

方法二：可以使用Map结构存储已经遍历的字符串的索引，判断当前字符是否已遍历过，如果已重复，索引为index，将不重复子串开始的索引重置为index + 1，继续遍历

  1. var lengthOfLongestSubstring = function(s) {
  2.   const length = s.length;
  3.   if (length === 0) return 0;
  4.   let len = 1;
  5.   let start = 0;
  6.   let end = 0;
  7.   const map = new Map();
  8.   while (end < length) {
  9.     const index = map.get(s[end]);
  10.     if (index >= start) {
  11.       start = index + 1;
  12.     }
  13.     len = len < end - start + 1 ? end - start + 1 : len;
  14.     map.set(s[end], end);
  15.     end++;
  16.   }
  17.   return len;
  18. };