老哥来看看跳槽常考算法呗 [第 1 期] 前端算法精选-字符串系列

很多前端工程师甚至很多研发工程师都缺乏数据结构和算知识，前端算法精选系列是一个针对常见的、高频的算法题做的一个算法解析系列，文章会给出详细的思路和解答，希望可以帮助到你。

无重复字符的最长子串

题目

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

示例 1：

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

示例 2：

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

示例 3：

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

解法

先看一下这道题的要求，它要求返回一个字符串中无重复字符的最大子串长度，时间复杂度和空间复杂度要求尽可能的低，有以下的思路

既然是最大子串的长度，首先最明显的思路就是维护一个最大不重复子串的变量和最大长度的变量。比如对于 “abcabcbb” 来说，维护一个 cur 来存当前最大不重复子串、max 维护最大长度，那么就有以下过程：

1. 遍历到 a，此时 cur=''，不包含'a'，所以 cur=cur+'a'='a'； cur 长度为 1 大于 max 的初始值 0，所以更新 max=1 ；

2. 遍历到 b，此时 cur='a'，不包含'b'，所以 cur=cur+'b'='ab'； cur 长度为 2 大于 max，所以更新 max=2 ；

3. 遍历到 c，此时 cur='ab'，不包含'c'，所以 cur=cur+'c'='abc'，cur 长度为 3 大于 max，所以更新 max=3 ；

4. 遍历到 a，此时 cur='abc'，包含'a'，所以截掉'a'以及它之前的字符串得到 cur='bc'，然后再加上这一轮的'a'，得到 cur='bca'； cur 长度为 3 不大于 max，所以不更新 max

5. 按照以上的逻辑继续遍历...

代码如下：

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    if(s.length === 0 || s.length === 1)  
        return s.length;
    let cur = '', max = '';
    for(let i = 0;i < s.length;i++) {
        const index = cur.indexOf(s[i]);
        if(index >= 0) {
            cur = cur.slice(index+1);
        }
        cur += s[i];
        if(cur.length >= max.length)
            max = cur;
    }
    
    return max.length;
};

最长公共前缀

题目

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

示例 1：

输入: ["flower","flow","flight"] 输出: "fl"

示例 2：

输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。

解法

这道题求一组字符串的最长公共前缀，思路可以转化成先以第一个字符串为最长公共前缀，然后跟第 2 个字符串对比，截取公共前缀部分，再跟第 3 个字符串对比，截取公共部分...依次进行下去，如果途中遇到公共前缀部分为空，则说明不存在公共前缀，函数返回空字符串。代码如下：

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
  if(strs.length === 0)
    return "";
  
  let prefix = strs[0];
  for(let i = 1;i < strs.length;i++) {
    let cur = strs[i];
    let index = 0;
    if(prefix === '')
      break;
    while(index < prefix.length && index < cur.length) {
      if(prefix[index] !== cur[index])
        break;
      index++;
    }
    prefix = prefix.slice(0, index);
    console.log(prefix);
  }
  
  return prefix;
};

欢迎关注前端亚古兽微信公众号，持续干货输出