4ms java solution, O(S + T) on average, O(S * T) worst case, O(T) space


  • 0
    Y

    Sequentially scan every char c in S. During the process, maintain an int array Prefix with length T, in which the i th element hold the number of founded prefix T[0 ~ i-1]. How do we update array Prefix? For each c you scan from S, find the index(or indices) of c in T which we write down as index(c), Simply update Prefix[ index(c) ] by adding Prefix[ index(c) - 1 ]. Explanation: Say if you have S "rabbbit", T"rabit" and you are currently scanning the second 'b' in S. You find that 'b' the number of prefix 'ra' is 1 and you simply add the number of founded prefix 'rab' by 1. which is 2 now.

    Map<Character, List<Integer>> map;
    	public int numDistinct(String s, String t) 
    	{
            int[] sumBuffer = new int[t.length()];
            map = new HashMap<Character, List<Integer>>();
            for(int i = 0; i < t.length(); i++)
            {
            	char c = t.charAt(i);
            	List<Integer> indices = map.get(c);
            	if(indices == null)
            	{
            		indices = new ArrayList<Integer>();
            		indices.add(i);
            		map.put(c, indices);
            	}
            	else
            	{
            		indices.add(i);
            	}
            }
            for(int i = 0; i < s.length(); i++)
            {
            	char c = s.charAt(i);
            	List<Integer> indices = map.get(c);
            	if(indices != null)
            	{
            		for(int j = indices.size()-1; j >=0; j--)
            		{
            			int index = indices.get(j);
            			if(index == 0)
            			{
            				sumBuffer[0]++;
            			}
            			else
            			{
            				sumBuffer[index] += sumBuffer[index-1];
            			}
            		}
            	}
            }
            return sumBuffer[t.length()-1];
        }
    

Log in to reply
 

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