DSA using Apex (Salesforce)- 01/100

Leetcode Q.20: Valid Parentheses

This will be an ongoing DSA series using Apex inside Salesforce

Question for today:

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.

Open brackets must be closed in the correct order.

Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Constraints:

• 1 <= s.length <= 10^4
• s consists of parentheses only '()[]{}'.

Pseudocode wrt to Salesforce :

1. Create a Map with open brackets as keys and their respective close brackets as their value
2. Take the string as input and convert it into an array of characters
3. Now create a list and whenever you encounter an open bracket, add it to this list.
4. Otherwise, check if it’s a matching bracket pair or not

Now let’s dive into the code :

Please go through the comments in the code:

public class BracketValidator {
    
    public static Map<String, String>bracketMap = 
     new Map<String, String>{'(' => ')','[' => ']','{' => '}'};
        
        public static Boolean isValid(String s) {
            try{
                if (s == null || s.length() == 0) { 
                    return false;
                }
                List<String> stack = new List<String>();
                List<String> charArray = s.split(''); //character array 
                
                return validate(charArray,0,stack);  
            }catch(exception e){
               system.debug('exception stack trace = '+e.getStackTraceString());
                return false;
            }
            
        }
    
    private static Boolean validate(List<String> charArray,
                                  Integer index,List<String> stack){

        if (index == charArray.size()) {
            return stack.isEmpty();
        }
        
        String ch = charArray[index];
        if(isOpening(ch)){
            stack.add(ch); //add opening brackets
        }else{
            if(index==0){ //save cpu time if first bracket is a closing bracket
                return false;
            }
            else if(stack.size()>0 && 
                   !isMatchingPair(stack?.remove(stack?.size()-1),ch)){ //not bracket pair
                return false;
            }else{
                if(stack.size()>0) stack.remove(0);
            }
            
        }
        return validate(charArray,index + 1,stack); // recursively call itself
    }
    
    private static Boolean isOpening(String ch){
        return  bracketMap.containsKey(ch);
    }
    
    private static Boolean isMatchingPair(String lastChar, String currentChar){
        return  bracketMap?.get(lastChar)== currentChar;
    }
    
}

The test cases are followed :

@isTest
public class BracketValidator_Test {
    
    @isTest static void positiveCase1(){
        String str = '()';
        Boolean b =BracketValidator.isValid(str);
        system.assertEquals(true,b);
    }
    @isTest static void positiveCase2(){
        String str = '()[]{}';
        Boolean b =BracketValidator.isValid(str);
        system.assertEquals(true,b);
    }
    @isTest static void positiveCase3(){
        String str = '[{()}]';
        Boolean b=BracketValidator.isValid(str);
        system.assertEquals(true,b);
    }
    @isTest static void negativeCase1(){
        String str = '';
        Boolean b=BracketValidator.isValid(str);
        system.assertEquals(false,b);
    }
    @isTest static void negativeCase2(){
        String str;
        Boolean b=BracketValidator.isValid(str);
        system.assertEquals(false,b);
    }
    @isTest static void negativeCase3(){
        String str='([}]';
        Boolean b=BracketValidator.isValid(str);
        system.assertEquals(false,b);
    }
    @isTest static void negativeCase4(){
        String str='}{()';
        Boolean b=BracketValidator.isValid(str);
        system.assertEquals(false,b);
    }
    @isTest static void negativeCase5(){
        String str='((}()';
        Boolean b=BracketValidator.isValid(str);
        system.assertEquals(false,b);
    }
    
}

If you have a better way to solve it, do let me know in the comments!

That’s all folks :)