程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> [LeetCode]Distinct Subsequences

[LeetCode]Distinct Subsequences

編輯:關於C++

dp經典題

題目

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ACE” is a subsequence of “ABCDE” while “AEC” is not).

Example
S> = “rabbbit”, T = “rabbit”

Return 3.

解題思路

解法一:依次遍歷兩個字符串,直到T遍歷結束,視為找到一個子串,這個就不用實現了 解法二:使用迭代思想,res表示T的第一個字符開始的子串能夠找到子序列個數。將T的第一個字符依次和S中的字符比較,如果相同,則計算T的下一位子串和S的下一位子串,結果累加如res中。
解法一和解法二都存在重復計算問題,思路簡單,但是大數據量時無法求解。

解法三:dp思想。

如果T[i] == S[j]則 dp[i][j] = dp[i][j + 1] + dp[i + 1][j + 1]
如果T[i] != S[j]則 dp[i][j] = dp[i][j + 1]
公式簡單,程序更簡單

解法四:類似於dp思想。數組dp[][] 第一維度表示T中第i個字符,第二維度表示上一個字符在S中開始找的位置,值表示T第i個可以在S第j位開始滿足子串查找的個數。
寫程序的時候感覺還行,現在想想感覺這個思路還是有點繞,用公式來理解的話比dp思路麻煩多了

程序

解法二

// 算法正確,遞歸不出來
public class Solution {
    /**
     * @param S, T: Two string.
     * @return: Count the number of distinct subsequences
     */
    public int numDistinct(String S, String T) {
        int res = 0;
        if(T.length() == 0 || S.length()

解法三

public class Solution {
    /**
     * @param S, T: Two string.
     * @return: Count the number of distinct subsequences
     */
    public int numDistinct(String S, String T) {
        if (T.length() == 0 || S.length() < T.length())
            return 0;

        int[][] dp = new int[T.length() + 1][S.length() + 1];
        Arrays.fill(dp[T.length()], 1);
        for (int i = T.length() - 1; i >= 0; i--) {
            for (int j = S.length() + i - T.length(); j >= 0; j--) {
                if (S.charAt(j) == T.charAt(i))
                    dp[i][j] = dp[i][j + 1] + dp[i + 1][j + 1];
                else
                    dp[i][j] = dp[i][j + 1];
            }
        }

        return dp[0][0];
    }
}

解法四

// 類dp解法
public class Solution {
    /**
     * @param S, T: Two string.
     * @return: Count the number of distinct subsequences
     */
    public int numDistinct(String S, String T) {
        int res = 0;
        if (T.length() == 0 || S.length() < T.length())
            return res;

        int[][] dp = new int[T.length()][S.length()];
        for (int i = T.length() - 1; i >= 0; i--) {
            for (int j = S.length() - 1; j >= 0; j--) {
                if (i == T.length() - 1) {
                    if (S.charAt(j) == T.charAt(i))
                        dp[i][j] = 1;
                } else {
                    if (S.charAt(j) == T.charAt(i)) {
                        int s = 0;
                        for (int k = j + 1; k < S.length(); k++)
                            s = s + dp[i + 1][k];
                        dp[i][j] = s;
                    }
                }
            }
        }
        int s = 0;
        for (int i = 0; i < S.length(); i++)
            s = s + dp[0][i];
        return s;
    }
}
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved