문자열2 [leetcode][10] Regular Expression Matching 문제 : leetcode.com/problems/regular-expression-matching/ 문자열 s와 패턴 p가 주어질 때 문자열 s가 패턴 p에 매칭되는지 판단하라. 패턴의 경우 나올 수 있는 문자는 총 3가지로, . * 소문자 알파벳 이 있다. . : 어떤 문자가 와도 매칭된다. * : 바로 앞에 나온 패턴 문자와 0개 이상 매칭된다. 소문자 알파벳 : 동일한 문자인 경우 매칭된다. . backtracking으로 구현. 2차원 배열을 만들어 memoization 해줬다. . 과 알파벳 소문자의 패턴인 경우는 문제될게 없다. . 는 무조건 통과이므로 s, p 모두 다음 문자를 확인한다. 소문자 알파벳은 다르다면 false, 같다면 다음 문자를 확인한다. 문제는 *. s = "aaaabb". .. 2021. 1. 22. KMP 알고리즘 만든 사람이 Knuth, Morris, Pratt 여서 Knuth–Morris–Pratt(KMP) 알고리즘이라 합니다. 문자열 알고리즘 중 하나로 문자열 에서 다른 문자열을 검색하는 알고리즘입니다. 단순하게 문자열(S) "ABCABDABCABC" 에서 문자열(P) "ABCABC"를 검색해봅시다. S, P 모두 가장 앞에서부터 같은지 비교합니다. (1) ~ (5) 는 문자가 같기 때문에 다음 문자를 비교합니다. (6) D, C는 다르기 때문에 문자열 P를 찾을 수 없습니다. 이제 S 문자열의 인덱스 1부터 다시 비교합니다. (1) B, A는 다르기 때문에 문자열 P를 찾을 수 없습니다. 문자열 P를 찾을 때까지 이를 반복합니다. 문자열 S 인덱스 6부터 시작하는 부분문자열에서 문자열 P를 찾을 수 있었습니.. 2020. 2. 9. 이전 1 다음
