算法---判断子序列(Kotlin)

题目

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

示例 1：

输入：s = “abc”, t = “ahbgdc”
输出：true
示例 2：

输入：s = “axc”, t = “ahbgdc”
输出：false

提示：

0 <= s.length <= 100
0 <= t.length <= 10^4
两个字符串都只由小写字符组成。

解决思路

方法1：
我们初始化两个指针 i 和 j，分别指向 s 和 t 的初始位置。每次贪心地匹配，匹配成功则 i 和 j 同时右移，匹配 s 的下一个位置，匹配失败则 j 右移，i 不变，尝试用 t 的下一个字符匹配 s。 最终如果 i 移动到 s 的末尾，就说明 s 是 t 的子序列。

方法二：

解决方法

方法1：

    fun isSubsequence(s: String, t: String): Boolean {
        var i = 0
        var j = 0
        val m = s.length
        val n = t.length
        while (i < m && j < n){
            if (s[i] == t[j]) {
                i++
            }
            j++
        }
        return i == m
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

方法2：

    fun isSubsequence2(s: String, t: String): Boolean {
        val m = s.length
        val n = t.length
        val dp = Array(m + 1) { Array(n + 1) { 0 } }

        for (i in 1..m) {
            for (j in 1..n) {
                if (s[i - 1] == t[j - 1]) {
                    dp[i][j] = dp[i-1][j-1] + 1
                } else {
                    dp[i][j] = dp[i][j-1]
                }
            }
        }
        //打印二维数组
        dp.forEach {
            it.forEach {
                print(it)
            }
            println()

        }
        return dp[m][n] == m
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

总结

1.越写算法越觉得自己编码能力还是太差
编码能力其实不是敲代码，而是解决问题的思路
这个是真的能判断出一个人聪明与否或者见识多少的
按照产品逻辑去写代码是另外一种基础能力
2.dp方程一定要清楚 不然二维数组少一个-1 结果都是错的