Description

Sort a linked list in $O(n log n)$ time using constant space complexity.

Analysis

We can solve this problem with DP solution. Here we use $num[i][j]$ to represent the number of sub-string $T[0..j]$ appearing in string $S[0...i]$.

So if $S[i] != T[j]$, then we know

and if $S[i] == T[j]$,

where $num[i-1][j-1]$ indicates the number of matches where we use $S[i]$ to match $T[j]$, while $num[i-1][j]$ indicates the number of matches where we do not use $S[i]$ to match $T[j]$.

As we can see, in the $i_{th}$ iteration, we only use information in ${i-1}_{th}$ iteration. Thus there is no need to save a 2D array, as all information in $1st..{i-2}_{th}$ iterations is useless. One thing worth noting that in the second layer of loop, we need to loop from $T.size()$ to $1$, i.e. in the reverse order. The reason is that if we iterate from $0..T.size()$, $num[i-1][j-1]$ will be overwritten by $num[i][j]$, then $num[i][j+1]$ will be calculated using $num[i][j]$ instead of $num[i-1][j]$, which is wrong.

Solution

 1 class Solution {
 2 public:
 3     int numDistinct(string S, string T) {
 4         int num[T.size()+1];
 5         memset(num, 0, sizeof(int) * (T.size()+1));
 6         num[0] = 1;  
 7         for (int i = 1; i <= S.size(); ++ i)
 8             for (int j = T.size(); j >= 1; -- j) // attention here: reverse iteration
 9                 if (S[i-1] == T[j-1])                                       
10                     num[j] += num[j-1];
11                    
12         return num[T.size()];
13     }
14 };