java dp solution beats 99%


  • 0
    H
    public class Solution {
        public int numDistinct(String s, String t) {
            int m = s.length(), n = t.length();
            if (n == 0 || n > m) return 0;
            
            char[] ss = s.toCharArray(), tt = t.toCharArray();
            int[] right = new int[n];
            int[] left = new int[n];
            
            int index = 0;
            for (int i = 0; i < n;) {
                if (tt[i] == ss[index])
                    right[i++] = index;
                index++;
                if (index == m && i != n) return 0;
            }
            
            index = m - 1;
            for (int i = n - 1; i >= 0;) {
                if (tt[i] == ss[index])
                    left[i--] = index;
                index--;
            }
            
            int[][] record = new int[m][n];
            recursive(record, m - 1, n - 1, right, left, ss, tt);
            
            return record[m - 1][n - 1];
        }
        
        public void recursive(int[][] record, int i, int j, int[] right, int[] left, char[] ss, char[] tt) {
            int bound = Math.min(left[j], i);
            for (int k = right[j]; k <= bound; k++) {
                if (tt[j] == ss[k]) {
                    if (j == 0) { record[i][j]++; continue; }
                    
                    if (record[k - 1][j - 1] == 0) recursive(record, k - 1, j - 1, right, left, ss, tt);
                    record[i][j] += record[k - 1][j - 1];    
                }
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.