用javascript分类刷leetcode20.字符串(图文视频讲解)2

 当`text1[i - 1] != text2[j - 1]`时：`dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])`;

 当 `j = 0` 时：`dp[i][0]=0`

var longestCommonSubsequence = function(text1, text2) {
    const m = text1.length, n = text2.length;
    const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));//初始化dp
    for (let i = 1; i <= m; i++) {
        const c1 = text1[i - 1];
        for (let j = 1; j <= n; j++) {
            const c2 = text2[j - 1];
            if (c1 === c2) {
                dp[i][j] = dp[i - 1][j - 1] + 1;//text1与text2字符相同时 最长公共子序列长度+1
            } else {
                  //text1与text2字符不同时 返回text1或text2向前减少一位之后的最长公共子序列中的较大者
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
};

var backspaceCompare = function(S, T) {
    let i = S.length - 1,
        j = T.length - 1,
        skipS = 0,
        skipT = 0;
    //双指针从右往左循环
    while(i >= 0 || j >= 0){
        while(i >= 0){//处理掉# 直到left指向的字符右边退格全部处理掉
            if(S[i] === '#'){
                skipS++;
                i--;
            }else if(skipS > 0){
                skipS--;
                i--;
            }else break;
        }
        while(j >= 0){//处理掉# 直到right指向的字符右边退格全部处理掉
            if(T[j] === '#'){
                skipT++;
                j--;
            }else if(skipT > 0){
                skipT--;
                j--;
            }else break;
        }
        if(S[i] !== T[j]) return false;//如果处理掉退格之后的字符串不相等，返回false
        i--;//继续循环
        j--;
    }
    return true;//如果循环过程中没返回false 最后就返回true
};

var removeInvalidParentheses = function (s) {
    let res = [];
    let queue = [];
    let visited = new Set();//去重

    queue.push(s);
    while (true) {
        let size = queue.length;//[s]
        for (let i = 0; i < size; i++) {
            s = queue.shift();//出队
            if (isVaild(s)) {//如果是合法字符串
                res.push(s);//加入结果数组
            } else if (res.length == 0) {//不合法并且res.length == 0 则进入bfs下一层 尝试删除字符
                for (let i = 0; i < s.length; i++) {
                    if (s[i] == '(' || s[i] === ')') {//是左右括号尝试删除字符，否则跳过
                        let nexts = s.substring(0, i) + s.substring(i + 1);
                        if (!visited.has(nexts)) {//判断新生成的字符串是否重复
                            queue.push(nexts);//加入队列 进入下一层 [s1,s2...]
                            visited.add(nexts);//加入去重数组
                        }
                    }
                }
            }
        }
        if (res.length > 0) {//出现合法字符串的那一层，终止循环
            break;
        }
    }
    return res;
};

function isVaild(s) {
    let count = 0;
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') {//左括号count+1
            count++;
        } else if (s[i] === ')') {//右括号count-1
            count--;
        }
        if (count < 0) {//小于0 说明右括号多
            return false;
        }
    }
    return count === 0;
}

 - `s[i-1] == t[j-1]`时：
   

   1.用`s[i - 1]`来匹配，`dp[i][j] = dp[i - 1][j - 1]`  ，  

   2.不用`s[i - 1]`来匹配，`dp[i][j] =  dp[i-1][j]`。

 - `s[i-1] != t[j-1]`时：就不能用`s[i - 1]`来匹配，`dp[i][j] = dp[i-1][j]`

 - `dp[i][0] =1`：当`j=0`时，相当于t是空字符串，空字符在另一个字符串的子串中出现一次，此时第一列都初始化为1。
 - 其他情况：初始化的时候`dp[i][j] =0`

//dp[i][j]表示以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]
const numDistinct = (s, t) => {
      //初始化dp数组，
    let dp = Array.from(Array(s.length + 1), () => Array(t.length +1).fill(0));
        //当j=0时，相当于t是空字符串，空字符在另一个字符串的子串中出现一次，此时第一列都初始化为1，
    for(let i = 0; i <=s.length; i++) {
        dp[i][0] = 1;
    }
    //当s[i-1] == t[j-1]：
      //1.用s[i - 1]来匹配 dp[i][j] = dp[i-1][j-1]
      //2.不用s[i - 1]来匹配 dp[i][j] = dp[i-1][j]
      //当s[i-1] != t[j-1]：不能用s[i-1]来匹配,s[i - 1]匹配不了t[j-1]，所以dp[i][j] = dp[i-1][j]
    for(let i = 1; i <= s.length; i++) {
        for(let j = 1; j<= t.length; j++) {
            if(s[i-1] === t[j-1]) {
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
            } else {
                dp[i][j] = dp[i-1][j]
            }
        }
    }

    return dp[s.length][t.length];
};

// "Let's take LeetCode contest"
const reverseWords = s => {
    const arr = s.split(' ');
    const res = [];
    for (let i = 0; i < arr.length; i++) {
        res.push(arr[i].split('').reverse().join(''));
    }
    return res.join(' ');
};

// "Let's take LeetCode contest"
var reverseWords = function (s) {
    let arr = s.split("");

    let l = 0, r = l;
    while (l < arr.length) {
        //找到结尾的空格
        while (arr[r] && arr[r] !== " ") {
            r++;
        }

        //反转单词
        for (let i = l, j = r - 1; i < j; i++, j--) {
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }

        //跳到下一个单词
        l = r + 1;
        r = l;
    }

    return arr.join("");
};

const longestValidParentheses = (s) => {
    let maxLen = 0;
    const len = s.length;
    const dp = new Array(len).fill(0);
    for (let i = 1; i < len; i++) {
        if (s[i] == ')') {//以')'结尾的字符才有效
            if (s[i - 1] == '(') {//如果前一个位置是'(' 则能与当前字符形成有效括号
                if (i - 2 >= 0) {//如果前2个位置还有字符串 
                    dp[i] = dp[i - 2] + 2;//当前状态等于 当前匹配的2个字符 加上 前两个位置匹配最长字符长度
                } else {//如果前2个位置没有字符串
                    dp[i] = 2;//当前状态等于 当前匹配的2个字符
                }
                //以i-1结尾的有效字符在向前看1个位置 如果是'(' 则能与当前字符形成有效括号
            } else if (s[i - dp[i - 1] - 1] == '(') {
                if (i - dp[i - 1] - 2 >= 0) {//以i-1结尾的有效字符在向前看2个位置 如果>=于0
                    //当前状态=以i-1结尾的有效字符长度 + 当前匹配2个有效括号 + 以i - dp[i - 1] - 2结尾的有效字符长度
                    dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2];
                } else {
                    //以i-1结尾的有效字符在向前看2个位置 如果<于0
                    //当前状态=以i-1结尾的有效字符长度 + 当前匹配2个有效括号 
                    dp[i] = dp[i - 1] + 2;
                }
            }
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
    return maxLen;
};

var longestValidParentheses = function (s) {
    let maxLen = 0
    let stack = []
    stack.push(-1) // 初始化一个参照物
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') {
            // ( 入栈   )出栈
            stack.push(i)
        } else {
            // )的情况 出栈
            stack.pop()
            if (stack.length) {
                // 每次出栈 计算下当前有效连续长度
                // 如何计算连续长度 当前位置 - 栈顶下标
                maxLen = Math.maxLen(maxLen, i - stack[stack.length - 1])
            } else {
                stack.push(i) //栈为空时 放入右括号参照物 表示从这个下标开始 需要重新计算长度
            }
        }
    }
    return maxLen
};

var longestValidParentheses = function (s) {
    let maxLen = 0;
    let left = 0;
    let right = 0;
    for (let i = 0; i < s.length; i++) {//从左往右
        if (s[i] == "(") {                //遇见'(' left++
            left++;
        } else {
            right++;                        //遇见')' right++
        }
        if (left == right) {              //左右数量相同
            maxLen = Math.max(maxLen, 2 * left);  //更新最大长度
        } else if (right > left) {        //right大于left 重置left right 重新计数
            left = right = 0;
        }
    }
    left = right = 0;
    for (let i = s.length - 1; i >= 0; i--) { //从右往左
        if (s[i] == "(") {
            left++;
        } else {
            right++;
        }
        if (left == right) {
            maxLen = Math.max(maxLen, right * 2);
        } else if (left > right) {
            left = right = 0;
        }
    }
    return maxLen;
};

f l o w e r
f l o w
f l i g h t

var longestCommonPrefix = function(strs) {
    if(strs.length == 0) 
        return "";
    let ans = strs[0];//ans初始值为字符串数组的第一个
    for(let i =1;i<strs.length;i++) {//循环字符串数组
        let j=0;
        for(;j<ans.length && j < strs[i].length;j++) {//循环字符，找到第一个不相同的位置
            if(ans[j] != strs[i][j])
                break;
        }
        ans = ans.substr(0, j);//从0号位置到第一个不相同的位置 截取字符串
        if(ans === "")
            return ans;
    }
    return ans;
};

输入: s = "aba"
输出: true

输入: s = "abca"
输出: true
解释: 你可以删除c字符。

function isPalindrome(str, l, r) {
    while (l < r) {   //对撞指针不断判断两边的数字是否相等         
        if (str[l] != str[r]) {
            return false;
        }
        l++;
        r--;
    }
    return true;
}

var validPalindrome = function (str) {
    let l = 0, r = str.length - 1; //头尾指针
    while (l < r) {
        if (str[l] != str[r]) {//左右指针不一样 还有一次机会，左指针向前一步或者右指针向后一步继续验证
            return isPalindrome(str, l + 1, r) || isPalindrome(str, l, r - 1);
        }
        l++;
        r--;
    }
    return true;
};

var longestPalindrome = function(s) {
    let n = s.length;
    let res = '';
    let dp = Array.from(new Array(n),() => new Array(n).fill(false));//初始化数组 
    for(let i = n-1;i >= 0;i--){//循环字符串
        for(let j = i;j < n;j++){
          //dp[i][j]表示子串i～j是否是回文子串
          //回文子串必须满足s[i]，s[j]相等。并且向外扩展一个字符也相等，即dp[i+1][j-1]也是回文子串
          //j - i < 2表示子串小于等于1也是回文串
            dp[i][j] = s[i] == s[j] && (j - i < 2 || dp[i+1][j-1]);
            if(dp[i][j] && j - i +1 > res.length){//当前回文子串比之前的大，更新最大长度
                res = s.substring(i,j+1);
            }
        }
    }
    return res;
};

var longestPalindrome = function (s) {
    if (s.length <= 0) {//边界条件
        return s;
    }

    let start = 0;//最长回文子串开始的索引
    let maxLength = 1;//初始化最大回文子串长度
    function h(left, right) {
        //当s[left]，和 s[right]想等时，不断向外扩展回文字符串的长度
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            if (right - left + 1 > maxLength) {
                maxLength = right - left + 1;//更新最大回文子串的长度
                start = left;//更新start的位置
            }
            left--;
            right++;
        }
    }

    for (let i = 0; i < s.length; i++) {
        h(i - 1, i + 1);//回文子串是奇数
        h(i, i + 1);//回文子串是偶数
    }

    return s.substring(start, start + maxLength);
};

var reverseWords = function(s) {
    return s.trim().replace(/\s+/g, ' ').split(' ').reverse().join(' ')
};

//"the sky is blue"
var reverseWords = function(s) {
    let left = 0
    let right = s.length - 1
    let queue = []
    let word = ''
    //去掉左右的空格
    while (s.charAt(left) === ' ') left ++
    while (s.charAt(right) === ' ') right --
    while (left <= right) {
        let char = s.charAt(left)
        if (char === ' ' && word) {
            queue.unshift(word)//字符串加入队列
            word = ''//重置字符串
        } else if (char !== ' '){//拼接单个字符串
            word += char
        }
        left++
    }
    queue.unshift(word)//最后一个字符串也要加入队列
    return queue.join(' ')//转回字符串
};