Share my java O(N) space 5ms, trimming string s before DP


  • 0
    C
    public class Solution {
        public int numDistinct(String s, String t) {
            if (t.isEmpty()) return 1;
            int i = s.indexOf(t.charAt(0));
            int j = s.lastIndexOf(t.charAt(t.length()-1));
            if (i < 0 || j < 0) return 0;
            s = s.substring(i, j+1);
            if (s.length() < t.length()) return 0;
            char[] ss = s.toCharArray();
            char[] tt = t.toCharArray();
            int pre[] = new int[ss.length+1];
            for (i = 0; i <= ss.length; ++i) pre[i] = 1;
            for (i = 0; i < tt.length; ++i) {
                int cur[] = new int[ss.length+1];
                for (j = i; j < ss.length; ++j) {
                    cur[j+1] = cur[j];
                    if (ss[j] == tt[i]) {
                        cur[j+1] += pre[j];
                    }
                }
                pre = cur;
            }
            return pre[ss.length];
        }
    }

Log in to reply
 

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