Solution by jasonzheng


  • 0
    J

    Approach #1 Matching parenthesis characters removal [Accepted]

    Algorithm
    We start the loop to scan the given string from the first character, and compare it with next character.

    If these two characters are a matching pair (we use a helper method for this as mentioned below), then remove this pair from the string, and reset the start index to 0 to start over for the new scan for the updated string.

    If these two characters are not a matching pair, increment the index to continue the loop.

    We use a helper method charPairMatch() to check if two characters are a matching pair or not.

    If the loop is complete and the remaining string is empty, it means all matching parentheses have been removed, thus the original string are valid parentheses. Otherwise, it is not.

    This approach guarantees that every character is visited only once.

    Java

    public class Solution {
    	public static boolean isValid(String input) {
    		boolean isValid = true;
    		if (input == null || input.isEmpty())
    			return false;
    		int start = 0;
    		int len = input.length();
    		int totalNum = 0;
    		while (input != null && !input.isEmpty() && totalNum < len -1) {
    			if (charPairMatch(input.charAt(start), input.charAt(start + 1))) {
    				input = input.substring(0, start) + input.substring(start + 2, input.length());
    				start = 0;
    				totalNum += 2;
    			} else {
    				start++;
    				totalNum++;
    			}
    		}
    		if (!input.isEmpty())
    			isValid = false;
    		return isValid;
    	}
    
    	private static boolean charPairMatch(char c1, char c2){
    		if ((c1=='{' && c2=='}') || (c1=='[' && c2==']') || (c1=='(' && c2==')')){
    			return true;
    		} else {
    			return false;
    		}
    	}
    }
    

    Complexity Analysis

    • Time complexity : $$O(n)$$. Each character will be visited once.

    • Space complexity : $$O(1)$$. Other than a couple variable definitions, it does not need extra space.


Log in to reply
 

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