java dynamic programming, beat 99%


  • 0
    H
    public class Solution {
        public int numDistinct(String s, String t) {
            int T = t.length();
            if (s.length() < T)
                return 0;
            int[] count = new int[T + 1]; 
            // count[i] means number of distinct subsequences of t.substring(0, i) in s
            count[0] = 1;
            HashMap<Character, List<Integer>> map = new HashMap<>();
            // <char, indices of this character in t in descending order>
            for (int i = T - 1; i >= 0; i--){
                char ch = t.charAt(i);
                List<Integer> list = null;
                if (map.containsKey(ch))
                    list = map.get(ch);
                else{
                    list = new ArrayList<Integer>();
                    map.put(ch, list);
                }
                list.add(i);
            }
            // System.out.println(map);
            for (char ch : s.toCharArray()){
                if (map.containsKey(ch)){
                    for (int ind : map.get(ch)){
                        count[ind + 1] += count[ind];
                    }
                }
            }
            return count[T];
        }
    }
    

Log in to reply
 

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