1、字符串

1、无重复字符的最长子串—*

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

var lengthOfLongestSubstring = function (s) {
    let max = 0;
    let frompos = 0;
    for (let i = 0; i < s.length; i++) {
        let pos = s.indexOf(s[i], frompos);
        if(pos > -1 && pos < i ) frompos = pos + 1;
        max = Math.max(max, i - frompos + 1);
    }
    return max;
};

var lengthOfLongestSubstring = function(s) {
    let substr = '', maxLength = 0;
    // find the next substring that longeer than previous to replace previous substring
    for (var i = 0; i < s.length; i++) {
        let findIndex = substr.indexOf(s[i]);
        if (~findIndex) {
            substr = substr.substring(findIndex + 1);
        }
        substr += s[i];
        if (substr.length > maxLength) {
            maxLength = substr.length;
        }
    }
    return maxLength;
};

let lengthOfLongestSubstring = function(s) {
    let map = new Map();
    let max = 0;
    for (let i = 0, j = 0; i < s.length && j < s.length; ++i) {
        let pos = map.get(s[i]);
        if (pos !== undefined) {
            j = Math.max(pos + 1, j);
        }
        max = Math.max(max, i - j + 1);
        map.set(s[i], i);
    }
    return max;
};

2、最长公共前缀—*

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

var longestCommonPrefix = function (strs) {
  let res = '';
  const tmp = strs[0] || '';
  let preModel = tmp.slice(0, 1);
  let cur = 1;
  const len = strs.length;
  if(len === 1) return tmp;
  while(cur <= tmp.length) {
    for(let i = 1; i < len; i++) {
      if(strs[i].indexOf(preModel) !== 0) return res;
    }
    res = preModel;
    preModel = tmp.slice(0, cur +1);
    cur++;
  }
  return res;
};

var longestCommonPrefix = function (strs) {
  let str = '';
  if (strs.length == 0) return str;
  let minL = strs[0].length;
  strs.forEach(item => {
    if (item.length < minL) {
      minL = item.length
    }
  })
  for (let i = minL; i > 0; i--) {
    let _str = strs[0].substr(0, i)
    let key = true;
    for (let j = 0; j < strs.length; j++) {
      let _strs = strs[j].substr(0, i)
      if (_strs != _str) {
        key = false;
        break;
      }
    }
    if (key) {
      str = _str;
      break
    }
  }
  return str;
};

var longestCommonPrefix = function(strs) {
    let prefix = ""
    if(strs.length <=0){
        return prefix
    }
    
    let minLength = strs[0].length
    for(let i=1;i<strs.length;i++){
        minLength = Math.min(minLength, strs[i].length)
    }
    
    for(let i=0;i< minLength;i++){
        let com = strs[0][i]
        for(let j=1;j<strs.length;j++){
            if(com != strs[j][i]){
                return prefix
            }
        }
        prefix = prefix + com
    }
    return prefix
};

3、字符串的排列

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

var isSameInOrder = function(s1, s2) {
  const order2 = s2.split('').sort().join('');
  return s1 === order2;
}
var checkInclusion = function (s1, s2) {
  const len1 = s1.length;
  const len2 = s2.length;
  if(len1 > len2) return false;
  const dislen = len2 - len1;
  const orders1 = s1.split('').sort().join('');
  for(let i = 0; i <= dislen; i++) {
    const substr = s2.substr(i, len1);
    if(isSameInOrder(orders1, substr)) return true;
  }
  return false;
};

const checkInclusion1 = function (s1, s2) {
  const count1 = Array(26).fill(0)
  const count2 = Array(26).fill(0)

  for (let i = 0; i < s1.length; i++) {
    count1[s1.charCodeAt(i) - 97]++
    count2[s2.charCodeAt(i) - 97]++
  }
  if (isSame(count1, count2)) {
    return true
  }
  for (let i = s1.length; i < s2.length; i++) {
    count2[s2.charCodeAt(i - s1.length) - 97]-- // 匹配串往后移一位
    count2[s2.charCodeAt(i) - 97]++
    if (isSame(count1, count2)) {
      return true
    }
  }
  return false
}

const isSame = (arr1, arr2) => {
  if (arr1.length !== arr2.length) {
    return false
  }
  for (let i = 0; i < arr1.length; i++) {
    if (arr1[i] !== arr2[i]) return false
  }
  return true
}

4、字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

var multiply = function(num1, num2) {
    if(num1 === '0' || num2 === '0') return '0';
    const len1 = num1.length;
    const len2 = num2.length;
    if(len1 > len2) {
      [num1, num2] = [num2, num1];
    }
    const arr1 = num1.split('');
    const arr2 = num2.split('');
    const tmp = {}; // 缓存计算过内容
    tmp['0'] = '0';
    tmp['1'] = num2;
    let mul = 1;
    for(var i = num1.length - 1; i >=0 ; i--) {
      mul
    }
};

5、翻转字符串里的单词

给定一个字符串，逐个翻转字符串中的每个单词。

var reverseWords = function(str) {
  const arr = str.replace(/(^\s*)|(\s*$)/g, '').replace(/\s+/g, ' ').split(' ');
  return arr.reverse().join(' ');
  // return str.trim().replace(/\s+/g, ' ').split(' ').reverse().join(' ');
};

let reverseWords = function(str) {
    let s = "";
    let c = "";
    for (let i = str.length - 1; i >= 0; --i) {
        if (c !== "" && str[i] === " ") {
            s += " " + c;
            c = "";
        }
        if (str[i] !== " ") {
            c = str[i] + c;
        }
    }
    if (c !== "") {
        s += " " + c;
    }
    return s.length > 0 ? s.substring(1) : "";
};

6、简化路径—*

输入："/a/./b/../../c/" 输出："/c"

var simplifyPath = function (path) {
  const dirArr = path.split('/');
  const curPath = [];
  for (let i = 0; i < dirArr.length; i++) {
    const cur = dirArr[i];
    if (cur === '..') {
      curPath.pop();
    } else if (cur === '.' || !cur) {
      
    } else {
      curPath.push(cur);
    }
  }
  return `/${curPath.join('/')}`;
};

var simplifyPath = function(path) {
    let arr = path.split('/');
    let res = [];
    for (let p of arr) {
        if (p === '..') {
            res.pop();
        } else if (p !== '' && p !== '.') {
            res.push(p);
        }
    }
    
    return '/' + res.join('/');
};

7、复原IP地址—*

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

var restoreIpAddresses = function(s) {
  const len = s.length;
  const res = [];
  if(len < 4 || len > 12) return res;
  splitStr(s, '', res, 0);
  return res;
};
function splitStr(str, last, res, count) {
  if (count === 3 && isValid(str)) {
    res.push(`${last}${str}`);
    return;
  }
  for(let i = 1; i < 4 && i < str.length; i++) {
    let curStr = str.substr(0, i);
    if(isValid(curStr)) {
      splitStr(str.substr(i), `${last}${curStr}.`, res, count + 1);
    }
  }
}
function isValid(num) {
  if (num[0] === '0') return num === '0';  
  return num <= 255 && num >= 0;
}

let restoreIpAddresses = function(s) {
    let res = [];
    helper(s, 0, 4, res, []);
    return res;
};

let helper = function(s, pos, parts, res, current) {
    if (parts === 0 && pos === s.length) {
        res.push(current.slice().join('.'));
    } else if (parts === 0 || pos === s.length) {
        return;
    } else {
        let pre = 0;
        for (let i = pos; i < s.length && (i === pos || pre > 0); ++i) {
            let val = pre * 10 + parseInt(s[i]);
            pre = val;
            if (val <= 255) {
                current.push(val);
                helper(s, i + 1, parts - 1, res, current);
                current.pop();
            } else {
                break;
            }
        }
    }
};