leetcode: Distinct Subsequences

問題描述：

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).

Here is an example:

S = 

"rabbbit"

, T = 

"rabbit"

Return 

3

.

原問題連結：https://leetcode.com/problems/distinct-subsequences/

問題分析

　　這個問題相對來說比較難找到思路。對于給定的源串s來說，要讓它的子串能夠構成目标串t，那麼理論上可能是它裡面的任何一個元素可能存在或者删除。如果按照這個思路，假設源串長度為m的話，那麼對它裡面每種情況進行構造并和目标串比較的可能性有2 ** m次。這種情況将使得解決方法不可接受。是以，我們需要根據原來的問題描述來尋找一個它們關系推導的規律。

　　假設對于s來說，它的目前位置為i，對于t來說它的目前位置為j。那麼當s.charAt(i)  != t.charAt(j)的時候，說明s串裡i這個位置的元素必須被删除才行，否則沒法比對。這個時候它們的可能構成數量和s[i - 1], t[j]的值相同。那麼，當s.charAt(i) == t.charAt(j)的話呢？那麼s[i - 1], t[j - 1]的情況是一種選擇。而s[i - 1], t[j]也是一種選項。這個地方有點難以了解，為什麼s[i - 1], t[j]也是一種選項呢？因為我們在前面的問題定義裡，對于s來說它裡面每個元素可能存在也可能删除。那麼當删除第i個元素的時候，也有可能它前面的i - 1個元素和t中間的j個元素也構成了符合條件的序列，是以這種情況也應該包含進來。

　　按照這個思路，我們可以定義一個二維矩陣int[][] matrix，它是一個(m + 1) x (n + 1)的矩陣。在最開始的時候，其中m, n分别表示s和t的長度。matrix[][]裡有一個初始條件，就是matrix[i][0] = 1。就是說，對于任意長度的源串s，對應于一個空串t來說，它都有一個子串，也就是删除它所有的字元。而對于其他的情況，則按照我們前面讨論的針對s.charAt(i - 1) == t.charAt(j - 1)的情況來處理。

　　于是我們可以得到如下的代碼實作：

public class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length();
        int n = t.length();
        if(n > m) return 0;
        int[][] matrix = new int[m + 1][n + 1];
        for(int i = 0; i <= m; i++) matrix[i][0] = 1;
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                matrix[i][j] = matrix[i - 1][j] + (s.charAt(i - 1) == t.charAt(j - 1) ? matrix[i - 1][j - 1] : 0);
            }
        }
        return matrix[m][n];
    }
}
           

　　這種實作的時間複雜度和空間複雜度基本上都是O(m * n) 。

改進

　　在上述的代碼實作中，我們還有一個可以改進的細節，就是對于空間的使用。前面的二維數組可以縮小為一維的數組，因為我們這裡隻需要保留t裡面對應每個長度的比對個數，我們可以重用之前的結果。

　　這種方式實作的代碼如下：

public class Solution {
    public int numDistinct(String s, String t) {
        int m = t.length();
        int n = s.length();
        if(m > n) return 0;
        int[] path = new int[m + 1];
        path[0] = 1;
        for(int j = 1; j <= n; j++) {
            for(int i = m; i >= 1; i--) {
                path[i] = path[i] + (t.charAt(i - 1) == s.charAt(j - 1) ? path[i - 1] : 0);
            }
        }
        return path[m];
    }
}