• 给定两个字符串S和T,返回S子序列等于T的不同子序列个数有多少个? 如果得到子序列A删除的位置与得到子序列B删除的位置不同,那么认为A和B就是不同的。


    问题描述:

            给定两个字符串S和T,返回S子序列等于T的不同子序列个数有多少个? 如果得到子序列A删除的位置与得到子序列B删除的位置不同,那么认为A和B就是不同的。
    【例子】
    S = "rabbbit", T = "rabbit"
    返回: 3
            是以下三个S的不同子序列,没有^的位置表示删除的位置,因为删除的位置不同,所以这三 个子序列是不一样的
            rabbbit
            I I I I II
            rabbbit
            I I I I II
            rabbbit
            I I I I II

    思想:

            看到题目题目中有两个字符串,讨论字符串之间的某种关系时,我们首先想到的是建立一张二维数组。

            建立二维数组dp[i][j],其含义是字符串S的0~i的子数组上随便删除得到的子序列与字符串T的0~j的子数组相同的方法数。

            二维数组第一行dp[0][j] 表示的含义是:字符串S第一个字符随便删除,变为字符串T的0~j的字符的方法数。我们知道只有第一个位置如果相等有一种方法,其他位置方法数为0。

            二维数组第一列dp[i][0] 表示的含义是:字符串S的0~i位置字符随便删除得到字符串T的第一个字符。dp[0][0]如果字符串T的第一个字符与字符串T的第一个字符相同则为1,不同则为0。字符串S的i位置字符与字符串S的第一个字符相同,则dp[i-1][0]+1,否则为dp[i-1][0]。

            对于二维数组的普遍位置dp[i][j]分为两种情况:

            1> 字符串S的第i个字符是处于删除状态时,dp[i][j] = dp[i-1][j] 。

            2> 字符串S的第i个字符是处于保留状态时,也就是S[i] = T[j],dp[i][j] = dp[i-1][j-1]

    代码:

    1. public static int maxSubSeqNum(String s,String t){
    2. if((s == null && t == null) || ("".equals(s) && "".equals(t))){
    3. return 1;
    4. }
    5. if((s == null && t != null) || s.length() < t.length()){
    6. return 0;
    7. }
    8. char[] sA = s.toCharArray();
    9. char[] tA = t.toCharArray();
    10. int[][] dp = new int[s.length()][t.length()];
    11. dp[0][0] = sA[0] == tA[0] ? 1 : 0;
    12. // dp[0][j] 其他不用填默认0
    13. // 列
    14. for (int i = 1; i < sA.length; i++) {
    15. dp[i][0] = sA[i] == tA[0] ? dp[i-1][0] + 1 : dp[i-1][0];
    16. }
    17. for (int i = 1; i < sA.length; i++) {
    18. for (int j = 1; j < tA.length; j++) {
    19. dp[i][j] = dp[i-1][j] + (sA[i] == tA[j] ? dp[i-1][j-1] : 0);
    20. }
    21. }
    22. return dp[sA.length-1][tA.length-1];
    23. }
    24. public static void main(String[] args) {
    25. String s = "abcvcabc";
    26. String t = "abc";
    27. System.out.println(maxSubSeqNum(s,t));
    28. }

  • 相关阅读:
    什么是跨域?跨域问题如何解决?看完豁然开朗。
    大一初学C时遇到比较难的题目
    关于Linux中作业调度 crond 和 systemd.timer 使用场景的一些笔记
    屏幕控制(2)
    打地鼠(susliks) 方法记录
    对象数组转成strin再进行,隔开的字符串,包括赛选某个字段的子,或者求和,
    请问有哪些让人惊艳的数据可视化工具?
    SpringSecurity源码学习二:异常处理
    【day6】类与对象、封装、构造方法
    四轴异常炸机分析讨论集锦
  • 原文地址:https://blog.csdn.net/z1171127310/article/details/128085827