무제 무제

문제 Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image! Example: Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Appr..

문제 Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. Example 1: Input: "(()" Output: 2 Explanation: The longest valid parentheses substring is "()" Example 2: Input: ")()())" Output: 4 Explanation: The longest valid parentheses substring is "()()" Approach 우선 Valid parentheses의 조건을 잘 생각해봐야한다. ')'가 나왔을 때 그 바로 전에 '(..

문제 Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.'.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). Note: s could be empty and contains only lowercase letters a-z. p could be empty and contains only lowercase letters a-z, and charact..

문제 Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example 1: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. Example 2: Input: "cbbd" Output: "bb" Approach Brute force로 접근. 인풋 스트링 길이에 해당하는 substring부터 길이를 1씩 줄이며 찾아나감 시간복잡도 O(n^3) Optimization Dynamic Programming O(n^2) 추가: Palindrome은 어떤 string이 palindrome일때 앞 ..