字符串篇五

子序列

方法一：自己想的用的非常辣鸡的栈的方法（shi）

class Solution {
    public boolean isSubsequence(String s, String t) {
        Stack<Character> stack1 = new Stack<>();
        Stack<Character> stack2 = new Stack<>();
        for (char c1 : s.toCharArray()) stack1.push(c1);
        for (char c2 : t.toCharArray()) stack2.push(c2);
        while (!stack2.isEmpty() && !stack1.isEmpty()) {
            if (stack2.peek() == stack1.peek()) {
                stack1.pop();
            }
            stack2.pop();
        }
        return stack1.isEmpty();
    }
}

方法二：双指针

给人的感觉就是这个方法跟上面我想的差不了多少，但是呢，我没有想到i == n这一点。

class Solution {
    public boolean isSubsequence(String s, String t) {
        int n = s.length(), m = t.length();
        int i = 0, j = 0;
        while(i < n && j < m){
            if(s.charAt(i) == t.charAt(j)){
                i++;
            }
            j++;
        }
        return i == n;
    }
}

方法三：动态规划

这个方法真是顶级

最后，是将26列均置为m而不是简单地把m列均置为m，因为这个今天已经错了好多次了

f[i][j]表示从字符i位置开始向后f[i][j]个位置字符j第一次出现的位置

import java.util.Arrays;

class Solution {
    public boolean isSubsequence(String s, String dictiobary) {
        int n = s.length(), m = dictiobary.length();
        int[][] f = new int[m + 1][26];
        //第m + 1行全部填上了m长度，其实m + 1行填上m就相当于最后一行是无穷大
        Arrays.fill(f[m], m);
        //for (int i = 0; i < 26; i++) f[m][i] = m;
        //将字典中的各个位置的字符字符记住
        for (int i = m - 1; i >= 0; i--) {
            for (int j = 0; j < 26; j++) {
                if (dictiobary.charAt(i) - 'a' == j) f[i][j] = i;
                else f[i][j] = f[i + 1][j];
            }
        }
        int add = 0;
        for (int i = 0; i < n; i++) {
            if (f[add][s.charAt(i) - 'a'] == m) return false;
            //这一句是没有else的，还有add = f[add][s.charAt(i) - 'a'] + 1;
            add = f[add][s.charAt(i) - 'a'] + 1;
        }
        return true;
    }
}

class Solution {
    public boolean isSubsequence(String s, String dictionary) {
        int m = s.length(), n = dictionary.length();
        if (m == 0)return true;
        if (m > n) return false;
        int[][] f = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s.charAt(i - 1) == dictionary.charAt(j - 1)) f[i][j] = f[i - 1][j - 1] + 1;
                else f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                if (f[i][j] == m) return true;
            }
        }
        return false;
    }
}

524. 通过删除字母匹配到字典里最长单词 - 力扣（LeetCode）

方法一：双指针

刚开始看到答案的时候理解不了t.compareTo(res) < 0这一句到底是干什么的

经过一节课的沉淀之后理解了(t.length() == res.length() && t.compareTo(res) < 0当字典中的两个单词长度一致时候，t.compareTo(res)可以比较二者的字典序。

class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        String res = "";
        for (String t : dictionary) {
            int i = 0, j = 0;
            while (i < t.length() && j < s.length()) {
                if (t.charAt(i) == s.charAt(j)) ++i;
                ++j;
            }
            if (i == t.length()) {
                //这里其实可以将t.length()换成i，效率会更高一些
                if (t.length() > res.length() || (t.length() == res.length() && t.compareTo(res) < 0)) {
                    res = t;
                }
            }
        }
        return res;
    }
}

方法二：排序（方法一的基础）

有一说一，这Lambda表达式真难写

class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        Collections.sort(dictionary,(a, b) ->{
            //如果长度不同，按照长度从大到小进行排序
            if (a.length() != b.length()) return b.length() - a.length();
            //如果长度相同，按照字典序进行排序
            return a.compareTo(b);
        });
        int n = s.length();
        for (String ss : dictionary){
            int m = ss.length();
            int i = 0, j = 0;
            while (i < n && j < m){
                if (s.charAt(i) == ss.charAt(j)) j++;
                i++;
            }
            if (j == m) return ss;
        }
        return "";
    }
}

展开来写就是这样

Collections.sort(dictionary, new Comparator<String>() {
    public int compare(String o1, String o2) {
        if (o1.length() != o2.length()) return o2.length() - o1.length();
        else return o1.compareTo(o2);
    }
});

方法三：动态规划写法

class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        // 动态规划写法
        int m = s.length();
        int[][] f = new int[m + 1][26];
        for (int i = 0; i < 26; i++)
            f[m][i] = m;
        for (int i = m - 1; i >= 0; i--) {
            for (int j = 0; j < 26; j++) {
                if (s.charAt(i) - 'a' == j)
                    f[i][j] = i;
                else
                    f[i][j] = f[i + 1][j];
            }
        }
        String ret = "";
        for (String ss : dictionary) {
            //一定要将这个写在循环体内部
            boolean flag = true;
            int len = ss.length();
            int add = 0;
            for (int i = 0; i < len; i++) {
                if (f[add][ss.charAt(i) - 'a'] == m) {
                    flag = false;
                    break;
                }
                add = f[add][ss.charAt(i) - 'a'] + 1;
            }
            if (flag) {
                if (ret.length() < ss.length() || (ret.length() == ss.length() && ss.compareTo(ret) < 0)) {
                    ret = ss;
                }
            }
        }
        return ret;
    }
}

522. 最长特殊序列 II - 力扣（LeetCode）

方法一：枚举法

我陷入了一个误区，就是这个is_Match函数的这两个参数，它的次序很重要，在findLUSlength的第二个for循环中，如果两个不同的字符串后面有一个字符串完全可以匹配当前（strs[i]字符串）字符串，就可以完全跳过当前（strs[i]字符串）去寻找下一个目标了，因为我你strs[i]字符串所拥有的字符我strs[j]全部都具有，strs[j]位置靠后，具有一定的绝对主动权(感觉这个应该也算是一种贪心吧)。（理解到位）

class Solution {
    //枚举每一个字符串
    public int findLUSlength(String[] strs) {
        int n = strs.length;
        int ret = -1;
        for (int i = 0; i < n; i++) {
            boolean flag = true;
            for (int j = 0; j < n; j++) {
                if (i != j && is_Match(strs[i], strs[j])){
                    flag = false;
                    break;
                }
            }
            if (flag){
                ret = Math.max(ret, strs[i].length());
            }
        }
        return ret;
    }

    public boolean is_Match(String s, String dictionary){
        int m = s.length(), n = dictionary.length();
        int i = 0, j = 0;
        while (i < m && j < n){
            if (s.charAt(i) == dictionary.charAt(j)) i++;
            j++;
        }
        return i == s.length();
    }

}

方法二：DP

这里需要最长公共子序列的DP基础，没学过，呜呜呜~~~，

class Solution {
    public int findLUSlength(String[] strs) {
        int n = strs.length, ans = -1;
        for (int i = 0; i < n; i++) {
            boolean flag = true;
            for (int j = 0; j < n; j++) {
                if (i != j && check(strs[i], strs[j])){
                    flag = false;
                    break;
                }
            }
            if (flag) ans = Math.max(ans, strs[i].length());
        }
        return ans;
    }
    boolean check(String s, String d){
        int len1 = s.length(), len2 = d.length();
        //如果我前面s的长度大于后面d的长度压根就不是你的子序列
        if (len1 > len2) return false;
        int[][] f = new int[len1 + 1][len2 + 1];
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (s.charAt(i - 1) == d.charAt(j - 1)) f[i][j] = f[i - 1][j - 1] + 1;
                else f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                if (f[i][j] == len1) return true;
            }
        }
        return false;
    }
}

1143. 最长公共子序列 - 力扣（LeetCode）

定义f[i][j]表示：s1[0 : i] 和s2[0 : j]的最长公共子序列的长度

上述表示种，s1[0 : i]表示s1长度为i的前缀，s2[0 : j]表示s2长度为j的前缀，

考虑动态规划的边界情况：

当 i = 0时候，s1[0 : i]为空，空字符串和任何字符串的最长公共子序列长度均为0，因此对于任意0 <= j <= m ，都有f[0][j] = 0
当 j = 0时候，s2[0 : j]为空，空字符串和任何字符串的最长公共子序列长度均为0，因此对于任意0 <= i <= m ，都有f[i][0] = 0

因此动态规划的边界情况是：当i或者j等于0的时候f[i][j] = 0。

当 i > 0 且 j > 0 的时候，，考虑f[i][j]的计算：

当s1[i - 1] = s2[j - 1]时，将这两个相同的字符串称为公共字符，考虑 s1[0 : i - 1] 和 s2[0 : j - 1] 的最长公共子序列，再增加一个字符（公共字符）即可得到s1[0 : i] 和s2[0 : j]的最长公共子序列因此 f[i][j] = f[i - 1][j - 1] + 1
当s1[i - 1] != s2[j - 1]时，考虑s1[0 : i] 和 s2[0 : j - 1] 的最长公共子序列和s1[0 : i - 1] 和 s2[0 : j] 的最长公共子序列。

class Solution {
    public int longestCommonSubsequence(String s1, String s2) {
		int m = s1.length(), n = s2.length();
        int[][] f = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) f[i][j] = f[i - 1][j - 1] + 1;
                else f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
            }
        }
        return f[m][n];
    }
}

算法

#leetcode

字符串篇五

http://example.com/2024/03/31/str5/

作者

nianjx

发布于

2024年3月31日

许可协议

字符串篇六上一篇

二叉搜索树下一篇