Skip to content

Instantly share code, notes, and snippets.

@guolinaileen
Created January 27, 2013 22:34
Show Gist options
  • Save guolinaileen/4651024 to your computer and use it in GitHub Desktop.
Save guolinaileen/4651024 to your computer and use it in GitHub Desktop.
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
public class Solution {
public boolean isValid(String s) {
int length=s.length();
char [] array=s.toCharArray();
if(length==0) return true;
Stack<Character> stack=new Stack<Character>();
for(int i=0; i<length; i++)
{
if(array[i]=='(' || array[i]=='{' || array[i]=='[' )
{
stack.push(array[i]);
}
if(array[i]==')' ||array[i]=='}' ||array[i]==']')
{
if(stack.isEmpty()) return false;
char temp=stack.pop();
if((temp=='(' && array[i]==')' ) || (temp=='{' && array[i]=='}' ) ||(temp=='[' && array[i]==']' ) )
{
continue;
}else
{
return false;
}
}
}
if(!stack.isEmpty()) return false;
return true;
}
}
@Ostap87
Copy link

Ostap87 commented Aug 10, 2019

<<>{>} - fail

@Ostap87
Copy link

Ostap87 commented Aug 10, 2019

public class Solution {
public boolean isValid(String input) {

Map<Character, Character> map = new HashMap<>();
    map.put('<', '>');
    map.put('{', '}');
    map.put('[', ']');
    map.put('(', ')');
 
 Stack<Character> stack = new Stack<>();
 
 for(char ch : input.toCharArray()){
     if(map.containsKey(ch)){
         stack.push(ch);
     } else if(!stack.empty() && map.get(stack.peek())==ch){
         stack.pop();
     } else {
         return false;
     }
 }
 return stack.empty();

}
}

@rossbu
Copy link

rossbu commented Sep 25, 2020

easy without extra space stack or queue but with 2 pointers ( pre,next)

 static boolean isValidParentheseUsing2Pointers(String testString) {
        if (testString == null || "".equals(testString)) return false;
        if (testString.length() % 2 != 0) return false;
        HashMap<Character, Character> hashMap = new HashMap<Character, Character>();
        hashMap.put('<', '>');
        hashMap.put('{', '}');
        hashMap.put('[', ']');
        hashMap.put('(', ')');
        char[] charArray = testString.toCharArray();
        for (int i = 0, j = i + 1; j < charArray.length; i = i + 2, j = i + 1) {
            char currentc = charArray[i];
            char nextc = charArray[j];
            char closingChar = hashMap.get(currentc);
            if (closingChar != nextc)
                return false;
        }
        return true;
    }

@Ameetrise
Copy link

how about this?

const isValid = function (s: string) {
let isTrue = true;
if (s.length % 2 === 0) {
let currentPointer = 0;
for (let i = 0; i < s.length; i++) {
let selectedPair = s.substring(currentPointer, currentPointer + 2);
if (
(selectedPair.length > 1 && selectedPair === '()') ||
selectedPair === '{}' || selectedPair === '[]'
) {
if (currentPointer + 4 <= s.length) {
currentPointer = currentPointer + 2;
}
} else {
isTrue = false;
}
}
} else {
isTrue = false;
}
console.log(isTrue);
};

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment