beat 99%,but I don't know if anyone has the same thought


  • 0
    J

    example1:
    S = "rabbbit", T = "rabbit"
    we have "ArrayList[] tIndex=new ArrayList[52]" to record something,
    tIndex[0]=1,tIndex[1]=2,3,tIndex[8]=4
    because in String T,a appear at 1,b appear at 2,3,i appear at 4 and so on.
    results[0] means how many "r" we have by far;
    results[1] means how many "ra" we have by far;
    results[2] means how many "rab" we have by far;
    ....
    results[5] means how many "rabbit" we have by far;that is what we need
    at first all results is 0.
    now we look at String S from start to end and update the results.
    "for(int i=0;i<s.length();i++)"
    now i=0,we is at 'r' in S,so result[0]=1,because we have a 'r' by far.
    and now i=1,we is at 'a' in S,so result[1]=1,because we already have a 'r' before and 'r'+'a'="ra",so we now have a "ra".
    now i=2,we is at 'b' in S,so result[2]=1.
    now i=3,we is at 'b'(the second one) in S,so result[2]=1+1, result[3]=1
    because we already have a "ra",so we have a new "rab",and add the old "rab",now we have two "rab",
    and with the new "b" ,we can form a "rabb".
    i=4,we is at 'b'(the third one) in S,,we can form some new "rab" and "rabb" so result[2]=2+1.result[3]=1+2.
    i=5,we is at 'i' in S,,we can form some new "rabbi" so result[4]=3.
    i=6,we is at 't' in S,,we can form some new "rabbit" so result[5]=3.
    class Solution {
    public int numDistinct(String s, String t) {
    if(t.length()==0)
    return 0;

        ArrayList[] tIndex=new ArrayList[52];
        for(int i=0;i<t.length();i++){
        	int index=0;
        	if(t.charAt(i)>='a')
        		index=t.charAt(i)-'a';
        	else
        		index=t.charAt(i)-'A'+26;
        	if(tIndex[index]==null)
        		tIndex[index]=new ArrayList();
        	tIndex[index].add(i);
        }
        
        int[] results=new int[t.length()];
        
        for(int i=0;i<s.length();i++){
        	int index=0;
        	
        	if(s.charAt(i)>='a')
        		index=s.charAt(i)-'a';
        	else
        		index=s.charAt(i)-'A'+26;
        	
        	if(tIndex[index]==null)
        		continue;
        	
        	for(int j=tIndex[index].size()-1;j>=0;j--){
        		int k=(Integer) tIndex[index].get(j);
        		if(k==0)
        			results[k]++;
        		else 
        		results[k]+=results[k-1];
        	}
        }
        return results[t.length()-1];
        
    }
    

    }


  • 0
    J
    This post is deleted!

Log in to reply
 

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