2019 算法面试相关(leetcode)--字符串

字符串相关的面试题还是挺多的，主要挑一些比较经典的leetcode上的题目说下。
一、反转字符串
不可谓不经典。

• 1.逆序遍历字符串，将字符存在一个新字符串上。

//这种方法时间和空间复杂度都是o(1),并不理想
var reverseString = function(s) {

   let res = ''

    for(let i = s.length - 1; i >= 0; i--){
        
        res += s[i]
    }

    return res
};

• 2.双指针法：遍历字符串，将对称位置上与当前位置上交换字符

//循环了n/2次，也没有占用多余的空间
var reverseString = function(s) {

    s = s.split('')
 
     for(let i = 0; i < ~~(s.length/2); i++){
 
         [s[i], s[s.length - i - 1]] = [s[s.length - i - 1], s[i]];
     }
 
     return s.join('')
 };

• 3.使用递归实现,参考反转链表
  递归函数存在的最大问题是，当递归次数足够大时，会导致函数栈溢出而死机，而函数栈的大小一般是一个固定值。
  使用递归实现的话，虽然时间复杂度也是o(n)，但在leetcode上却由于栈开销过大从而导致未通过。
  所以递归不适用于较大字符串的情况。

var reverseString = function(s) {

    if(s.length <= 1) return s

    return reverseString(s.substring(1)) + s[0]
 };

二、无重复字符的最长子串
比较容易想到的是暴力遍历，时间复杂度是o(n^3),太过暴力，这里不再赘述。

• 双指针+滑动窗口
  维护一个滑动窗口，遍历字符串，如果下个字符s[j]在当前滑动窗口里，则窗口从左开始移除元素，直至s[j]不在该窗口里，再继续循环，记录窗口的最大长度

var lengthOfLongestSubstring = function(s) {
    
    if(s.length == 0) return 0;

    let maxLength = 1;

    let i = j = 0;

    let map = {};

    while(i < s.length - maxLength & j < s.length){
        
        if(s[j] in map){

            delete map[s[i++]]

        }else{

            map[s[j++]] = 0
            
            maxLength = Math.max(maxLength,j - i); 
        }
    }

    return maxLength;
};

三、 最长公共前缀
首先找出数组中最短字符串的长度，接下来的遍历就不用超过这个长度。
接下来选取数组第一个字符串当作基准，逆序遍历，直至找出其余字符串的前缀是该子串为止

var longestCommonPrefix = function(strs) {

    if(!strs.length) return ""

    let str = strs[0], minLength = str.length

    for(let i = 1; i < strs.length; i++){

        minLength = Math.min(minLength,strs[i].length)
    }
    
    for(let j = minLength - 1; j >= 0 ; j--){

        let tmp = str.substring(0,j + 1)

        let isPre = true;

        for(let i = 1; i < strs.length; i++){

            if(strs[i].indexOf(tmp) != 0){
                
                isPre = false

                break;
            } 
        }

        if(isPre) return tmp
    }

    return ""
};