20. Valid Parentheses

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.

Example 1:

Input: s = "()"
Output: true
Plain Text
복사

Example 2:

Input: s = "()[]{}"
Output: true
Plain Text
복사

Example 3:

Input: s = "(]"
Output: false
Plain Text
복사

Constraints:

•

1 <= s.length <= 104

•

s consists of parentheses only '()[]{}'.

My solution

문자열 s 가 주어진다. '(', ')', '{', '}', '[', ']'를 포함한다.

입력된 문자열이 유효한지 확인하라.

아래의 조건을 만족할 때 유효하다.

여는 괄호는 같은 타입의 괄호로 닫혀야만 한다.

여는 괄호는 올바른 순서로 닫아야 한다.

Example 1:

Input: s = "()"
Output: true
Plain Text
복사

인풋으로 들어오는 대로 배열(스택)에 쌓는다.

처음에는 하나 넣어둔 상태로 시작하는 게 좋을 거 같다.

for문에 들어가자마자 스택의 top에 있는 괄호를 확인해서 검사하는 방식으로 한다.

이 때 올바른 괄호로 닫힌다면 괄호의 쌍을 제거한다.

올바른 여는 괄호라면 스택의 top으로 추가시킨다.

만약 더이상 남은 s가 없으면 for문을 나가서 stack에 남은 문자열이 있다면 false를 반환하고 아니면 true를 반환한다.

const str = s.split('');
const stack = [];

for(let i : 0 ~ arr.length)
	if(여는 괄호면) {
		stack.push
	} else if(스택이 비어있을 때 || (닫는 괄호일 때 스택의 top이 일치하지 않는 경우들){
		return false;
	} else {
		stack.pop();
	}
}
return stack.length===0;
JavaScript
복사

위와 같이 하면 하드코딩이고 괄호가 늘어날 때 수정해야할 코드가 많다.

하지만 map이라는 객체를 만들어 대응하는 괄호들을 검사하도록 하면 조건문을 줄일 수 있다.

const str = s.split('');
  const stack = [];
  const map = {
    ')': '(',
    ']': '[',
    '}': '{',
  };

  for (let i = 0; i < arr.length; i++) {
    if (!map[arr[i]]) { // map에 대응하는 괄호가 없는 경우(즉, 여는 괄호인 경우)
      stack.push(arr[i]);
    } else if (!stack.length || stack.pop() !== map[arr[i]]) { 
			// 스택이 비었거나 스택에 있는 괄호를 꺼내서 올바르지 않은 경우면
      return false;
    }
  }
  return stack.length === 0;
JavaScript
복사

속도면에서는 첫번째 솔루션이 조금 2배정도 빠르게 나왔다.(63 > 145)

Code

/**
 * @param {string} s
 * @return {boolean}
 */
const isValid = function (s) {
  const str = s.split('');
  const stack = [];
  for (let i = 0; i < str.length; i++) {
    if (str[i] === '(' || str[i] === '[' || str[i] === '{') {
      stack.push(str[i]);
    } else if (
      !stack.length ||
      (str[i] === ')' && stack[stack.length - 1] !== '(') ||
      (str[i] === ']' && stack[stack.length - 1] !== '[') ||
      (str[i] === '}' && stack[stack.length - 1] !== '{')
    ) {
      return false;
    } else {
      stack.pop();
    }
  }
  return stack.length === 0;

  // sol2
  // const str = s.split('');
  // const stack = [];
  // const map = {
  //   ')': '(',
  //   ']': '[',
  //   '}': '{',
  // };
  // for (let i = 0; i < str.length; i++) {
  //   if (!map[str[i]]) {
  //     stack.push(str[i]);
  //   } else if (!stack.length || stack.pop() !== map[str[i]]) {
  //     return false;
  //   }
  // }
  // return stack.length === 0;
};

describe('isValid', () => {
  it('TC1', () => {
    expect(isValid('()')).toStrictEqual(true);
  });
  it('TC2', () => {
    expect(isValid('()[]{}')).toStrictEqual(true);
  });
  it('TC3', () => {
    expect(isValid('(]')).toStrictEqual(false);
  });
});
JavaScript
복사