6ms Java O(n) space


  • 0
    A
    public class Solution {
        public int numDistinct(String s, String t) {
            if(t.length() > s.length()) return 0;
            int[] count = new int[t.length()];
            char[] arrt = t.toCharArray();
            char[] arrs = s.toCharArray();
            Map<Character, LinkedList<Integer>> m = new HashMap<Character, LinkedList<Integer>>();
            LinkedList<Integer> temp = null;
            int i = 0;
           //keep a list of indexes of the same character
            for(char c : arrt){
                temp = m.get(c);
                if(temp == null){
                    temp = new LinkedList<Integer>();
                    m.put(c, temp);
                }
                temp.addFirst(i++);
            }
            // count[i] = count[i]+count[i-1]
            for(char c : arrs){
                temp = m.get(c);
                if(temp != null){
                    for(int k : temp){
                        if(k == 0){
                            count[k]++;
                        }else{
                            count[k] += count[k-1];
                        }
                    }
                }
            }
            return count[t.length()-1];
        }
    }

Log in to reply
 

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