Meet TLE with long input string sequence, can anyone help me with my code?


  • 0
    H

    I try to get full permutation of the String array L and then check if S contains each of the permutation and add each index into my result and return. Since the process of getting full permutation need recursion, so it is time consuming, can anyone help me with my code? Or I need to give up this one and figure out other thought.

      public static void swap(String[] str, int i, int j){  
        String temp = new String();  
        temp = str[i];  
        str[i] = str[j];  
        str[j] = temp; 
    } 
    
    public static void permutation (String[] L, int st, ArrayList<String> re){
        if (st == L.length - 1){
        	String temp = new String();
            for (int i = 0; i < L.length; i ++){
                temp +=L[i];
            }  
            re.add(temp);
        }else{
            for (int i = st; i < L.length; i ++){  
                swap(L, st, i);  
                arrange(L, st + 1,re);  
                swap(L, st, i);  
            }  
        }  
        return ;
    }  
    public static ArrayList<Integer> findSubstring(String S, String[] L) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        ArrayList<String> possible = new ArrayList<String>();
        
        permutation(L,0,possible);//get full permutation
        
        for(int j= 0; j<possible.size();j++){
        	if(S.contains(possible.get(j)))
        		result.add(S.indexOf(possible.get(j))); 	
        }
       
        return result;
    }

Log in to reply
 

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