字符串

双指针

用两个指针来定位一个子数组，其中一个指针指向数组的第 1 个数字，另一个指针指向数组的最初一个数字，那么两个指针之间所蕴含的就是一个子数组。

能够在挪动这两个指针的同时，统计两个指针之间的字符串中字符呈现的次数，这样能够解决很多常见的面试题，如在一个字符串中定位另一个字符串的变位词等。

因为这种类型的面试题都与统计字母呈现的次数无关，咱们常常应用哈希表来存储每个元素呈现的次数，因而解决这种类型的面试题通常须要同时应用双指针和哈希表。

14. 字符串中的变位词

题目：输出字符串 s1 和 s2，如何判断字符串 s2 中是否蕴含字符串 s1 的某个变位词？如果字符串 s2 中蕴含字符串 s1 的某个变位词，则字符串 s1 至多有一个变位词是字符串 s2 的子字符串。假如两个字符串中只蕴含英文小写字母。例如，字符串 s1 为 ”ac”，字符串 s2 为 ”dgcaf”，因为字符串 s2 中蕴含字符串 s1 的变位词 ”ca”，因而输入为 true。如果字符串 s1 为 ”ab”，字符串 s2 为 ”dgcaf”，则输入为 false。

由变位词的定义可知，变位词具备以下几个特点。首先，一组变位词的长度肯定雷同；其次，组成变位词的字母汇合肯定雷同，并且每个字母呈现的次数也雷同。

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var checkInclusion = function(s1, s2) {if(s2.length < s1.length) {return false;}

    var areAllZero = function(counts) {for(let i of counts) {if(i !== 0) {return false}
        }
        return true;
    }

    const counts = new Array(26).fill(0)

    for(let i = 0; i < s1.length; i++) {counts[s1.charCodeAt(i) - 97]++;
        counts[s2.charCodeAt(i) - 97]--;
    }
    if(areAllZero(counts)) {return true;}

    for (let i = s1.length; i < s2.length; ++i) {counts[s2.charCodeAt(i) - 97]--
        counts[s2.charCodeAt(i - s1.length) - 97]++

        if(areAllZero(counts)) {return true}
    }
    return false;
};

15. 字符串中的所有变位词

题目：输出字符串 s1 和 s2，如何找出字符串 s2 的所有变位词在字符串 s1 中的起始下标？假如两个字符串中只蕴含英文小写字母。例如，字符串 s1 为 ”cbadabacg”，字符串 s2 为 ”abc”，字符串 s2 的两个变位词 ”cba” 和 ”bac” 是字符串 s1 中的子字符串，输入它们在字符串 s1 中的起始下标 0 和 5。

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s1, s2) {if(s2.length > s1.length) {return [];
    }

    let result = [];

    const counts = new Array(26).fill(0);

    var areAllZero = function(counts) {for(let i of counts) {if(i !== 0) {return false}
        }
        return true;
    }

    for(let i = 0; i < s2.length; i++){counts[s2.charCodeAt(i)-97]++
        counts[s1.charCodeAt(i)-97]--
    }

    if(areAllZero(counts)) {result.push(0)
    }

    for(let i = s2.length; i < s1.length; i++) {counts[s1.charCodeAt(i)-97]--
        counts[s1.charCodeAt(i-s2.length)-97]++

        if(areAllZero(counts)) {result.push(i-s2.length+1)
        }
    }

    return result;
};

16. 不含反复字符的最长子字符串

题目：输出一个字符串，求该字符串中不含反复字符的最长子字符串的长度。例如，输出字符串 ”babcca”，其最长的不含反复字符的子字符串是 ”abc”，长度为 3。

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {if(s.length == 0) return 0
    if(s.length == 1) return 1

    const map = new Map();
    let max = 0
    // 双指针
    let left = 0
    let right = 0

    var areAllZero = function(counts) {for(let i of counts) {if(i[1] === 2) {return false}
        }
        return true;
    }

    while(right < s.length) {if(map.get(s.charAt(right)) !== 1) {map.set(s.charAt(right), (map.get(s.charAt(right)) || 0) + 1)
            right++
            if(map.get(s.charAt(right)) === 1) {max = Math.max(right - left, max)
            }
        } else {map.set(s.charAt(left), (map.get(s.charAt(left)) || 0) - 1)
            left++
        }
    }
    max = Math.max(right - left, max)

    return max;
};

17. 蕴含所有字符的最短字符串

输出两个字符串 s 和 t，请找出字符串 s 中蕴含字符串 t 的所有字符的最短子字符串。例如，输出的字符串 s 为 ”ADDBANCAD”，字符串 t 为 ”ABC”，则字符串 s 中蕴含字符 ’A’、’B’ 和 ’C’ 的最短子字符串是 ”BANC”。如果不存在符合条件的子字符串，则返回空字符串 ””。如果存在多个符合条件的子字符串，则返回任意一个。

var minWindow = (s, t) => {const charToCount = new Map();
    
    for(let ch of t) {charToCount.set(ch, (charToCount.get(ch) || 0) + 1)
    }
    let count = charToCount.size;
    let start = 0, end = 0, minStart = 0, minEnd = 0;
    let minLength = Infinity;
    while(end < s.length || (count == 0) && end == s.length) {if(count > 0) {let endCh = s.charAt(end);
            if(charToCount.get(endCh)!== undefined) {charToCount.set(endCh, charToCount.get(endCh)-1)
                if (charToCount.get(endCh) === 0) {count--}
            }
        } else {if (end - start < minLength) {
                minLength = end - start
                minStart = start
                minEnd = end
            }
            let startCh = s.charAt(start);
            if(charToCount.get(startCh)!==undefined) {charToCount.set(startCh, charToCount.get(startCh) + 1)
                if(charToCount.get(startCh) == 1) {count++}
            }
            start++
        }
    }

    return minLength < Infinity ? s.substring(minStrat, minEnd) : "";
}

上述代码中只有一个 while 循环，用来把两个变量从 0 减少到字符串 s 的长度。如果字符串的长度是 n，那么工夫复杂度就是 O（n）。能够应用一个哈希表来统计每个字符呈现的次数。哈希表的键为字符，假如字符串中只有英文字母，那么哈希表的大小不会超过 256，辅助空间的大小不会随着字符串长度的减少而减少，因而空间复杂度是 O（1）。

回文字符串

18. 无效的回文

给定一个字符串 s，验证 s 是否是 回文串，只思考字母和数字字符，能够疏忽字母的大小写。

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    let l = 0;
    let r = s.length - 1;
    const reg = /[a-zA-Z0-9]/
    while(l <= r) {if(!reg.test(s.charAt(l))) {
            l++
            continue
        }
        if(!reg.test(s.charAt(r))) {
            r--
            continue
        }
        if(s.charAt(r).toLocaleLowerCase() !== s.charAt(l).toLocaleLowerCase()) {return false} else {
            l++
            r--
        }
    }
    return true
};

19. 最多删除一个字符失去回文

给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符是否失去一个回文字符串。

/**
 * @param {string} s
 * @return {boolean}
 */
var validPalindrome = function (s) {
  let low = 0,
    high = s.length - 1;
  const valid = (low, high) => {for (let i = low, j = high; i < j; i++, j--) {if (s[i] != s[j]) return false;
    }
    return true;
  };
  while (low < high) {if (s[low] == s[high]) {
      low++;
      high--;
    } else {return valid(low + 1, high) || valid(low, high - 1);
    }
  }
  return true;
};

我没有思考到 2 种状况都让他执行

20. 回文子字符串的个数

题目：给定一个字符串，请问该字符串中有多少个回文间断子字符串？例如，字符串 ”abc” 有 3 个回文子字符串，别离为 ”a”、”b” 和 ”c”；而字符串 ”aaa” 有 6 个回文子字符串，别离为 ”a”、”a”、”a”、”aa”、”aa” 和 ”aaa”。

后面都是从字符串的两端开始向里挪动指针来判断字符串是否是一个回文, 其实也能够换一个方向从字符串的核心开始向两端延长。如果存在一个长度为 m 的回文子字符串，则别离再向该回文的两端延长一个字符，并判断回文前后的字符是否雷同。如果雷同，就找到了一个长度为 m + 2 的回文子字符串。

/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function(s) {if(s == null || s.length == 0) {return 0}

    let count = 0;
    for(let i = 0; i < s.length; i++) {count += countPalindrome(s, i, i)
        count += countPalindrome(s, i, i + 1)
    }
    return count
};

var countPalindrome = function(s, start, end) {
    let count = 0;
    while(start >= 0 && end < s.length && s.charAt(start) == s.charAt(end)) {
        count++
        start--
        end++
    }
    return count;
}

上述解法依然须要两个嵌套的循环，因而工夫复杂度是 O（n2）。该解法只用到了若干变量，其空间复杂度是 O（1）。

总结