[Arogorithm]문자열

대표적인 문자열 유형인 회문과 가로열에 대해 알아보자...

📝 회문

• 앞 뒤 방향으로 볼 때, 같은 순서의 문자로 구성된 문자열을 의미한다.
• 쉽게 좌우 대칭이라 보면 된다. 

    public static boolean isPalindrome(String str) {
        int left = 0;
        int right = str.length() - 1;

        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

 

📝 올바른 괄호 문자열

• 올바른 괄호 문자열이란 모든 괄호가 적절히 짝을 이루고 잇는 문자열을 의미한다.
• 예를 들어 (), {}, [] 모두 올바른 괄호 문자열이다. 
• 보통 스택을 통해 검증한다. 

    public static boolean isValidParentheses(String str) {
        Stack<Character> stack = new Stack<>();

        for (char ch : str.toCharArray()) {
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            } else if (ch == ')' || ch == '}' || ch == ']') {
                if (stack.isEmpty()) {
                    return false;
                }
                char openBracket = stack.pop();
                if (!isMatchingPair(openBracket, ch)) {
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }

    private static boolean isMatchingPair(char openBracket, char closeBracket) {
        return (openBracket == '(' && closeBracket == ')') ||
               (openBracket == '{' && closeBracket == '}') ||
               (openBracket == '[' && closeBracket == ']');
    } 해당 방식으로 풀 수 있다

그런데 너무 복잡하지 않아??

📌 치환

• 모든 괄호에 대해 '('를 1로, ')'을 -1로 치환하면 쉽게 풀 수 있다.
• 문자열 s를 모두 순회하여 합 계산을 하는 것