Java solution with O(n^2), beat 1%!!!


  • 0
    W

    no kidding, brute force implementation without extra space.

    '''public boolean isValid(String s) {

    	if (s.isEmpty() || s == null) return false;
        if (s.length()%2 != 0) return false; 
        System.out.println ("input = " + s);
        
        boolean[] visited = new boolean[s.length()]; 
        for (int i = 0; i < s.length() -1; i++){
            visited[i] = false;
        }
        
        char left;
        int lefts = 0;
        int rights = 0;
        for (int i = 0; i < s.length() -1; ){
            visited[i] = true; 
            left = s.charAt(i);
            if (!isValidLeft(left)) { 
            	rights ++; 
            	i++; 
            	if (rights > lefts) {
            		return false; 
            	} else { 
            		continue;
            	}
            }
            else {
            	lefts ++;
            }
            
            if (!foundValidRight(s, left, visited, i)) {
            	 System.out.println ("not valid!");
            	 return false;
            } else {
            	i++;
            }
        }
        return true;
    }
    
    public boolean isValidLeft(char c) {
        if (c == '{' || c == '(' || c == '[' ) return true; 
        return false;
    }
    
    public boolean foundValidRight(String s, char c, boolean[] visited, int indexLeft) {
        int right = foundRightIndex(s, c, visited, indexLeft); 
        //System.out.println ("char = " + c);
        //System.out.println (" left = " + indexLeft + ", right = " + right); 
        if (right == -1) return false;
        if ((right + indexLeft)%2 == 1) {           
            return true; 
        }
        return false;
    }
    
    private int foundRightIndex(String s, char c, boolean[] visited, int indexLeft) {
        if (indexLeft < 0 || indexLeft > s.length() -1) return -1; 
        int indexRight = indexLeft + 1;
        int lefts = 1; // how many same left chars being encountered before reaching corresponding right char
        while (lefts > 0 && indexRight < s.length()){
            
                if (s.charAt(indexRight) == c){
                    lefts ++;
                    indexRight ++;
                    continue;
                }
                        
                switch (c) {
                    case '{': 
                        if (s.charAt(indexRight) == '}'){
                        	if (!visited[indexRight])
                        		visited[indexRight] = true;
                        	lefts --;
                        }                        
                        break;
                    case '[': 
                        if (s.charAt(indexRight) == ']'){
                        	if (!visited[indexRight])
                        		visited[indexRight] = true;
                        	lefts --;
                        }                        
                        break;
                    case '(': 
                        if (s.charAt(indexRight) == ')'){
                        	if (!visited[indexRight])
                        		visited[indexRight] = true;
                        	lefts --;
                        }                        
                        break;
                   default: 
                        break;
                }   
                
                if (lefts == 0) // found!
                    break;
                    
                indexRight ++;
        }
        if (lefts == 0) { //found corresponding right char
            visited[indexRight] = true;
            return indexRight;
        } else { // not found 
            return -1;
        }
    }
    

    '''


  • 0

    @whyseahike said in Java solution with O(n^2), beat 1%!!!:

    ited = new boolean[s.l

    You use extra space by allocating the array boolean visited[].
    You can check my solution that doesn't use extra space, but it is written in C: https://discuss.leetcode.com/topic/96482/simple-solution-with-o-0-memory-overhead-with-pointers


Log in to reply
 

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