Why i got a TLE problem?my algorithm complexity is O(n)


  • 0
    P

    this is my code:`

    	public String minWindow(String S, String T) {
    
    	int start=0;
    	Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    	int count =Integer.MAX_VALUE;
    	int key=0;
    	String storge=T;
    	for (int i = 0; i < S.length(); i++) {
    		char temp = S.charAt(i);
    		if (storge.contains(String.valueOf(temp))) {
    			if(storge.length()==T.length())start=i;
    			storge=storge.replaceFirst(String.valueOf(temp), "");
    		}
    		if(storge.length()==0){
    			map.put(start, i);
    			start=i+1;
    			storge=T;
    		}
    	}
    	if(map.size()==0)return null;
    	for (Integer item:map.keySet()) {
    		int temp=map.get(item)-item;
    		if(temp<count){
    			count=temp;
    			key=item;
    		}
    	}
    	return S.substring(key,map.get(key)+1);
    }

  • 3
    M

    This algorithm isn't quite O(n). Let s=S.length() and t=T.length(). While you only have the 1 explicit loop, causing O(s), you also have an implicit loop inside String.replaceFirst(). String.replaceFirst() creates a copy of the list before it does anything, taking O(t) time since every element you try to replace is known to be in S. Since this occurs O(s) times, the time complexity is O(st), or basically O(n^2).


Log in to reply
 

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