搞定大厂算法面试之leetcode精讲20.字符串

原创

全栈潇晨

修改于 2021-12-04 07:34:25

6200

修改于 2021-12-04 07:34:25

文章被收录于专栏：高级前端工程师学习必备高级前端工程师学习必备

搞定大厂算法面试之leetcode精讲20.字符串

视频讲解（高效学习）:点击学习

方法1.动态规划

ds_100

思路：定义dp[i][j]表示子串i～j是否是回文子串，循环s的子串，看是否满足s[i]，s[j]相等，如果相等，则dp[i][j]是否为回文串取决于dp[i+1][j-1]是否也是回文子串，在循环的过程中不断更新最大回文子串的长度，注意子串的长度是0或1也算回文子串
复杂度：时间复杂度O(n^2)，两层循环。空间复杂度O(n^2)，即动态规划dp数组的空间。

Js:

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;
};

Java:

public String longestPalindrome(String s) {
    int N = s.length();
    boolean[][] dp = new boolean[N][N];
    String res = "";

    for (int i = N - 1; i >= 0; i--) {
        for (int j = i; j < N; j++) {
            if (s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
            }
            if (dp[i][j] && (j - i + 1) > res.length()) {
                res = s.substring(i, j + 1);
            }
        }
    }
    return res;
}

方法2.中心扩散法

ds_99

思路：分最长回文子串是奇数和偶数的情况，定义start为最长回文子串开始的索引，然后循环字符串，不断不断向外扩展回文字符串的长度，循环的过程中更新最大回文子串的长度和start的位置，最后返回start到start+ maxLength的子串就是本题的答案
复杂度：时间复杂度O(n^2)，循环字符串一次，每次循环内部又向外不断扩张。空间复杂度O(1)

Js:

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);
};

Java:

class Solution {
    public String longestPalindrome(String s) {

        if (s == null || s.length() < 1) {
            return "";
        }

        //定义最长回文子串的长度
        int maxLength = 1;
        //定义最长回文子串的起始位置
        int start = 0;
        
        //遍历可能的回文子串的中心位置
        for (int i = 0; i < s.length() - 1; i++) {
            //最长回文子串的长度为奇数时，中心位置为一个字符
            int oddLength = expandAroundCenter(s, i, i);
            //最长回文子串的长度为偶数时，中心位置为两个字符
            int evenLength = expandAroundCenter(s, i, i + 1);
            int length = Math.max(oddLength, evenLength);

            //找出最大长度
            if (maxLength < length) {
                maxLength = length;
                //计算start位置
                start = i - (maxLength - 1) / 2;
                
            }
        }
        //截取字符串
        return s.substring(start, start + maxLength);
    }

    //返回最长回文子串的长度
    public int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length()) {
            if (s.charAt(left) == s.charAt(right)) {
                //边界向外扩展
                left--;
                right++;
            } else {
                break;
            }
        }
        //最后一次向外扩展不满足条件，还原该次扩展
        left++;
        right--;
        return right - left + 1;
    }
}

680. 验证回文字符串 Ⅱ （easy）

思路：对撞指针不断判断左右两边的数字是否相等，如果不相等还有一次机会，左指针向前一步或者右指针向后一步继续验证
复杂度：时间复杂度O(n)，空间复杂度O(1)。

例子：

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

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

js：

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;
};

java：

class Solution {
    public boolean validPalindrome(String s) {
        int l = 0, r = s.length() - 1;
        while (l < r) {
            char c1 = s.charAt(l), c2 = s.charAt(r);
            if (c1 == c2) {
                ++l;
                --r;
            } else {
                return validPalindrome(s, l, r - 1) || validPalindrome(s, l + 1, r);
            }
        }
        return true;
    }

    public boolean validPalindrome(String s, int l, int r) {
        for (int i = l, j = r; i < j; ++i, --j) {
            char c1 = s.charAt(i), c2 = s.charAt(j);
            if (c1 != c2) {
                return false;
            }
        }
        return true;
    }
}

32. 最长有效括号（hard）

方法1.动态规划

思路：dp[i]表示以i结尾的最长有效括号的长度，分为4种情况，看图
复杂度：时间复杂度O(n)，n是字符串的长度，总共遍历1次。空间复杂度O(n)，即dp数组的空间

ds_10

js:

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;
};

Java:

class Solution {
    public int longestValidParentheses(String s) {
        int maxLen = 0;
        int[] dp = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxLen = Math.max(maxLen, dp[i]);
            }
        }
        return maxLen;
    }
}

方法2.栈

思路：遍历字符串，准备一个栈，存放字符串下标，首先放入初始参照物-1，遇到'('入栈，遇到')'出栈，并且判断栈长度，如果不为空，更新最大合法字符串长度，否则将当前下标放入栈中
复杂度：时间复杂度O(n)，n是字符串的长度，总共遍历1次。空间复杂度O(n)，即栈的空间

动画过大，点击查看

js:

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
};

java:

class Solution {
    public int longestValidParentheses(String s) {
        int maxLen = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    maxLen = Math.max(maxLen, i - stack.peek());
                }
            }
        }
        return maxLen;
    }
}

方法3.两次遍历

思路：从左到右，从右到左依次遍历字符串，遇见'(' , left++，遇见')' , right++，当左右括号数量相同时，更新最大长度，如果right大于left，则重置left、right 重新计数
复杂度：时间复杂度O(n)，n是字符串的长度，总共遍历2次。空间复杂度O(1)

ds_12

Js:

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;
};

Java:

class Solution {
    public int longestValidParentheses(String s) {
        int left = 0, right = 0, maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxLen = Math.max(maxLen, 2 * right);
            } else if (right > left) {
                left = right = 0;
            }
        }
        left = right = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxLen = Math.max(maxLen, 2 * left);
            } else if (left > right) {
                left = right = 0;
            }
        }
        return maxLen;
    }
}

301. 删除无效的括号（hard）

方法1:bfs

ds_111

思路：最少删除的括号数量，这种求最短或者最少的题目，联想到bfs，bfs第一个出现解的层，即为最短删除括号所形成的合法字符串。准备queue对字符串进行bfs搜索，出现合法字符串入队，否则尝试删除一个字符，进入下一层判断，注意合法字符可能重复，需要去重。

js：

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;
}

java：

public class Solution {

    public List<String> removeInvalidParentheses(String s) {
        List<String> res = new ArrayList<>();
        if (s == null) {
            return res;
        }

        Set<String> visited = new HashSet<>();
        visited.add(s);
        Queue<String> queue = new LinkedList<>();
        queue.add(s);

        boolean found = false;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String front = queue.poll();
                if (isValid(front)) {
                    res.add(front);
                    found = true;
                }

                int currentWordLen = front.length();
                char[] charArray = front.toCharArray();
                for (int j = 0; j < currentWordLen; j++) {
                    if (front.charAt(j) != '(' && front.charAt(j) != ')') {
                        continue;
                    }

                    String next = new String(charArray, 0, j) + new String(charArray, j + 1, currentWordLen - j - 1);
                    if (!visited.contains(next)) {
                        queue.offer(next);
                        visited.add(next);
                    }
                }
            }

            if (found) {
                break;
            }
        }
        return res;
    }

    public boolean isValid(String s) {
        char[] charArray = s.toCharArray();
        int count = 0;
        for (char c : charArray) {
            if (c == '(') {
                count++;
            } else if (c == ')') {
                count--;
            }
            if (count < 0) {
                return false;
            }
        }
        return count == 0;
    }
}

387. 字符串中的第一个唯一字符（easy）

方法1:哈希表

思路：统计字符出现的频次，找出第一个频次为1的字符的索引
复杂度：时间复杂度O(n)，空间复杂度O(k)，k是字符集大小

js：

var firstUniqChar = function (s) {
    const counts = new Array(26).fill(0); //长度为26的数组，存放字符的出现次数

    for (const c of s) { //遍历s，统计每个字符出现次数
        counts[c.charCodeAt(0) - 97]++; //97是a的Unicode值
    }
    for (let i = 0; i < s.length; i++) { //再次遍历s
        if (counts[s[i].charCodeAt(0) - 97] == 1) {//找出第一个频次为1的字符的索引
            return i;
        }
    }
    return -1;
};

java：

class Solution {
    public int firstUniqChar(String s) {
        Map<Character, Integer> frequency = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            frequency.put(ch, frequency.getOrDefault(ch, 0) + 1);
        }
        for (int i = 0; i < s.length(); ++i) {
            if (frequency.get(s.charAt(i)) == 1) {
                return i;
            }
        }
        return -1;
    }
}

方法2:队列

思路：循环字符串s，如果map中未出现当前字符，则将字符串和位置索引加入map和队列中，当出现重复字符时，map中的字符对应的value设置成-1，如果队头元素对应在map中的value是-1，说明是重复元素，不断出队，直到队头是不重复的元素。循环结束之后，如果队列中存在元素，队头就是第一个不重复的字符
复杂度：时间复杂度O(n)，空间复杂度O(k)，k是字符集大小

js：

var firstUniqChar = function(s) {
    const position = new Map();
    const q = [];
   
    for (let [i, ch] of Array.from(s).entries()) {
      //循环字符串s，如果map中未出现当前字符，则将字符串和位置索引加入map和队列中
        if (!position.has(ch)) {
            position.set(ch, i);
            q.push([ch, i]);
        } else {
            position.set(ch, -1);//当出现重复字符时 map中的字符对应的value设置成-1
          //如果队头元素对应在map中的value是-1，说明是重复元素，不断出队，直到队头是不重复的元素
            while (q.length && position.get(q[0][0]) === -1) {
                q.shift();
            }
        }
    }
    return q.length ? q[0][1] : -1;//如果队列中存在元素，队头就是第一个不重复的字符
};

java：

class Solution {
    public int firstUniqChar(String s) {
        Map<Character, Integer> position = new HashMap<Character, Integer>();
        Queue<Pair> queue = new LinkedList<Pair>();
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            char ch = s.charAt(i);
            if (!position.containsKey(ch)) {
                position.put(ch, i);
                queue.offer(new Pair(ch, i));
            } else {
                position.put(ch, -1);
                while (!queue.isEmpty() && position.get(queue.peek().ch) == -1) {
                    queue.poll();
                }
            }
        }
        return queue.isEmpty() ? -1 : queue.poll().pos;
    }

    class Pair {
        char ch;
        int pos;

        Pair(char ch, int pos) {
            this.ch = ch;
            this.pos = pos;
        }
    }
}

14. 最长公共前缀（easy）

思路：纵向扫描字符串，找到第一个不相同的位置
复杂度：时间复杂度O(mn)，m是字符串最长长度，n是字符数组长度

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

js：

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;
};

java：

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0) 
            return "";
        String ans = strs[0];
        for(int i =1;i<strs.length;i++) {
            int j=0;
            for(;j<ans.length() && j < strs[i].length();j++) {
                if(ans.charAt(j) != strs[i].charAt(j))
                    break;
            }
            ans = ans.substring(0, j);
            if(ans.equals(""))
                return ans;
        }
        return ans;
    }
}

344. 反转字符串（easy）

思路：指针left初始时指向0号位置，right初始指向n-1的位置。双指针不断交换left和right位置的元素
复杂度：时间复杂度O(n)。空间复杂度O(1)

js：

var reverseString = function(s) {
    const n = s.length;
   //双指针不断交换left和right位置的元素
    for (let left = 0, right = n - 1; left < right; left++, right--) {
        [s[left], s[right]] = [s[right], s[left]];
    }
};

java：

class Solution {
    public void reverseString(char[] s) {
        int n = s.length;
        for (int left = 0, right = n - 1; left < right; left++, right--) {
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
        }
    }
}

151. 翻转字符串里的单词 (medium)

方法1:正则

思路：将字符串头尾空格去掉，然后将那个多个空格用正则替换成一个空格，根据空格分隔成数组，然后翻转转回字符串

js：

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

java：

class Solution {
    public String reverseWords(String s) {
        s = s.trim();
        List<String> wordList = Arrays.asList(s.split("\\s+"));
        Collections.reverse(wordList);
        return String.join(" ", wordList);
    }
}

方法2:双端队列

思路：left指针初始在0号位置，right指针初始在s.length - 1位置，遍历字符串，将每个由空格分隔的字符串加入队列，最后在转回字符串就是翻转过后的了
复杂度：时间复杂度O(n)，空间复杂度O(n)

js：

//"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(' ')//转回字符串
};

java:

class Solution {
    public String reverseWords(String s) {
        int left = 0, right = s.length() - 1;
        while (left <= right && s.charAt(left) == ' ') {
            ++left;
        }

        while (left <= right && s.charAt(right) == ' ') {
            --right;
        }

        Deque<String> d = new ArrayDeque<String>();
        StringBuilder word = new StringBuilder();
        
        while (left <= right) {
            char c = s.charAt(left);
            if ((word.length() != 0) && (c == ' ')) {
                d.offerFirst(word.toString());
                word.setLength(0);
            } else if (c != ' ') {
                word.append(c);
            }
            ++left;
        }
        d.offerFirst(word.toString());

        return String.join(" ", d);
    }
}

1143. 最长公共子序列 (medium)

方法1:动态规划

ds_151

ds_152

思路：注意子序列可以不连续
1. 状态定义：dp[i][j]表示 text1[0:i-1] 和 text2[0:j-1] 的最长公共子序列，注意是闭区间，之所以是到i-1或j-1，是方便初始化dp数组，当i=0或者j=0的时候表示的就是空字符和另一个字符串匹配，此时的dp[i][j]=0
2. 状态转移方程：当text1[i - 1] == text2[j - 1]时：dp[i][j] = dp[i - 1][j - 1] + 1 当text1[i - 1] != text2[j - 1]时：dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
3. dp的初始化：当 i = 0 时：dp[0][j]=0 当 j = 0 时：dp[i][0]=0
4. 返回结果：dp[len(text1)][len(text2)]
复杂度：时间复杂度O(mn)，空间复杂度O(mn)

js：

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];
};

java：

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            char c1 = text1.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                char c2 = text2.charAt(j - 1);
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}

115. 不同的子序列 (hard)

方法1.动态规划

ds_153

ds_154

思路：拆分成不同子串的匹配，这些匹配存在重复子结构，可以用动态规划来做
1. 状态定义：dp[i][j]表示以i-1为结尾的s，它的子序列中出现以j-1为结尾的t的个数为dp[i][j]
2. 状态转移方程：
  - 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]
3. 初始状态：
  - dp[i][0] =1：当j=0时，相当于t是空字符串，空字符在另一个字符串的子串中出现一次，此时第一列都初始化为1。
  - 其他情况：初始化的时候dp[i][j] =0
复杂度：时间复杂度O(mn)，m，n分别是s和t的长度。空间复杂度O(mn)，dp数组的空间

js：

//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];
};

java：

class Solution {
    public int numDistinct(String s, String t) {
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        for (int i = 0; i < s.length() + 1; i++) {
            dp[i][0] = 1;
        }
        
        for (int i = 1; i < s.length() + 1; i++) {
            for (int j = 1; j < t.length() + 1; j++) {
                if (s.charAt(i - 1) == t.charAt(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()];
    }
}

125. 验证回文串（easy）

思路：用正则去掉无关字符，然后对撞指针判断左右两边是否是相同的字符

复杂度：时间复杂度O(n)，空间复杂度O(1)

js：

var isPalindrome = function (s) {
    s = s.replace(/[\W|_]/g, "").toLowerCase();
    if (s.length < 2) {
        return true;
    }
    let left = 0;
    let right = s.length - 1;
    while (left < right) {
        if (s[left] !== s[right]) {//对撞指针判断左右两边是否是相同的字符
            return false;
        }
        left++;
        right--;
    }
    return true;
};

java：

public boolean isPalindrome(String s) {
    String lowerCase = s.toLowerCase();

    int left = 0;
    int right = lowerCase.length() - 1;
    while (left < right) {
        while (left < right && !Character.isLetterOrDigit(lowerCase.charAt(left))) {
            left++;
        }

        while (left < right && !Character.isLetterOrDigit(lowerCase.charAt(right))) {
            right--;
        }

        if (lowerCase.charAt(left) != lowerCase.charAt(right)) {
            return false;
        }

        left++;
        right--;
    }

    return true;
}

796. 旋转字符串 (easy)

思路：字符串重复一次判断是否包含另一个字符串
复杂度：时间复杂度O(n^2)，比较一个字符串是否包含另一个字符串的复杂度O(n^2)。空间复杂度O(n)

var rotateString = function (A, B) {
    return A.length <= B.length && (A + A).includes(B)
};

java：

class Solution {
    public boolean rotateString(String A, String B) {
        return A.length() == B.length() && (A + A).contains(B);
    }
}

844. 比较含退格的字符串 (easy)

ds_184

方法1.截取字符串，循环字符串，遇到#就截掉最后一个字符，循环完毕之后，最后比较两个去除掉#退格之后的字符串是否相等，时间复杂度O(m+n)，m、n是两个字符串的长度。空间复杂度O(1)

方法2.双指针

思路：双指针从右往左循环，每次循环两个字符处理掉#，直到第一个字符是右边退格全部处理掉之后的字符，然后看这两个字符是否一致
复杂度：时间复杂度O(m+n)，m、n是两个字符串的长度。空间复杂度O(1)

js：

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
};

java：

class Solution {
    public boolean backspaceCompare(String S, String T) {
        int i = S.length() - 1, j = T.length() - 1;
        int skipS = 0, skipT = 0;

        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                if (S.charAt(i) == '#') {
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    skipS--;
                    i--;
                } else {
                    break;
                }
            }
            while (j >= 0) {
                if (T.charAt(j) == '#') {
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }
            if (i >= 0 && j >= 0) {
                if (S.charAt(i) != T.charAt(j)) {
                    return false;
                }
            } else {
                if (i >= 0 || j >= 0) {
                    return false;
                }
            }
            i--;
            j--;
        }
        return true;
    }
}

557. 反转字符串中的单词 III (easy)

方法1:借助api

// "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(' ');
};

方法2:双指针

js：

// "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("");
};

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

腾讯广告算法大赛

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

腾讯广告算法大赛