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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1732 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

无重复字符的最长子串

题目

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

示例 1：

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

示例 2：

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

示例 3：

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

解法

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

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

遍历到 a，此时 cur=''，不包含'a'，所以 cur=cur+'a'='a'； cur 长度为 1 大于 max 的初始值 0，所以更新 max=1 ；
遍历到 b，此时 cur='a'，不包含'b'，所以 cur=cur+'b'='ab'； cur 长度为 2 大于 max，所以更新 max=2 ；
遍历到 c，此时 cur='ab'，不包含'c'，所以 cur=cur+'c'='abc'，cur 长度为 3 大于 max，所以更新 max=3 ；
遍历到 a，此时 cur='abc'，包含'a'，所以截掉'a'以及它之前的字符串得到 cur='bc'，然后再加上这一轮的'a'，得到 cur='bca'； cur 长度为 3 不大于 max，所以不更新 max
按照以上的逻辑继续遍历...

代码如下：

/**
 * @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;
};

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

第 1 条附言 · 2020-02-28 10:13:38 +08:00

[第 2 期] 👉https://v2ex.com/t/648174#reply0

第 2 条附言 · 2020-02-28 13:39:51 +08:00

更新解法

发现之前的解法时间复杂度比较高，在最坏的情况下复杂度是O(n^2)；所以优化一下，用空间换时间，维护一个map存储当前字符串每个字符出现的次数；时间复杂度O(n)，空间复杂度O(n) 之前写的比较急，感谢老哥指出问题


/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    if(s.length === 0 || s.length === 1)  
        return s.length;
    let cur = '', max = 0, map = {};
    for(let left = 0, right = 0;right < s.length;right++) {
        const rightChar = s[right];
        if(map[rightChar]) {
            map[rightChar]++;
        } else {
            map[rightChar] = 1;
        }
        
        // 如果发现重复的字符，会从左侧一直删除，直到重复的字符已经被删除为止
        while(map[rightChar] > 1) {
            const leftChar = s[left];
            map[leftChar]--;
            left++;
        }
        if(right - left + 1 > max) {
            max = right - left + 1;
        }
    }
    
    return max;
};

cur

字符

length

Max

30 条回复 • 2020-02-28 22:41:14 +08:00