Leetcode_10_정규 표현 식 일치 Leetcode44_WildcardMatching 모호 일치
1. Leetcode10_정규 표현 식 일치
1. 제목 소개:
*Leetcode_10_RegularExpressionMatching_Hard
* https://leetcode.com/problems/regular-expression-matching/
* Given an input string (s) and a pattern (p), implement regular expression
* matching with support for '.' and '*'.
* (1)、'.' Matches any single character.
* (2)、'*' 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 characters like . or *.
* Example 1:
* Input:
* s = "aa"
* p = "a"
* Output: false
* Explanation: "a" does not match the entire string "aa".
* Example 2:
* Input:
* s = "aa"
* p = "a*"
* Output: true
* Explanation: '*' means zero or more of the preceding element, 'a'.
* Therefore, by repeating 'a' once, it becomes "aa".
* Example 3:
* Input:
* s = "ab"
* p = ".*"
* Output: true
* Explanation: ".*" means "zero or more (*) of any character (.)".
* Example 4:
* Input:
* s = "aab"
* p = "c*a*b"
* Output: true
* Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".
* Example 5:
* Input:
* s = "mississippi"
* p = "mis*is*p*."
* Output: false
2. 사고 분석
* ：
* ，'?' ； '.';
* '*' ;
* '*' ， 0 、1 。
* ， ，'*' ；
* ，'*' , "a*" ".*" 。
* ：
* ：
* ① ps[i]!='*' , ： ；
* dp[i][j] = dp[i - 1][j - 1] && (ps[i - 1] == '.' || ps[i - 1] == ss[j - 1])
* ② ps[i]=='*' , :
* A. * 0, ps[i-1] ， dp[i][j]=i > 1 && dp[i - 2][j];
* B. * 1， ， (dp[i][j - 1]==true)，
* ps[i-2] '.' ss[j-1] 。(i-2 i 1 lp )。3. JAVA 코드
public boolean isMatch(String s, String p) {
if (s != null && s.equals(p)) return true;
char[] ss = s.toCharArray(), ps = p.toCharArray();
int ls = ss.length, lp = ps.length;
// dp
boolean[][] dp = new boolean[lp + 1][ls + 1];
dp[0][0] = true;
for (int i = 1; i <= lp; i++)//
dp[i][0] = i > 1 && ps[i - 1] == '*' && dp[i - 2][0];
for (int i = 1; i <= lp; i++) {
if (ps[i - 1] == '*') {
for (int j = 1; j <= ls; j++) {//
//* ：
// ：dp[i][j] = (i > 1 && dp[i - 2][j])
// ：.* a* ， ：
// dp[i][j] =(dp[i][j - 1] && (ps[i - 2] == '.' || ps[i - 2] == ss[j - 1]))
// ：
dp[i][j] = (i > 1 && dp[i - 2][j]) ||
(dp[i][j - 1] && (ps[i - 2] == '.' || ps[i - 2] == ss[j - 1]));
}
} else {
for (int j = 1; j <= ls; j++) // ： dp[i - 1][j - 1]
dp[i][j] = dp[i - 1][j - 1] && (ps[i - 1] == '.' || ps[i - 1] == ss[j - 1]);
}
}
return dp[lp][ls];
}
2. Leetcode44_WildcardMatching 모호 일치
1. 제목 소개
* Leetcode_44_WildcardMatching_Hard
*
* https://leetcode.com/problems/wildcard-matching/
* ：
* Given an input string (s) and a pattern (p), implement wildcard pattern
* matching with support for '?' and '*'.
* 1. '?' Matches any single character.
* 2. '*' Matches any sequence of characters (including the empty sequence).
* 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 characters like ? or *.
* Example 1:
* Input:
* s = "aa"
* p = "a"
* Output: false
* Explanation: "a" does not match the entire string "aa".
* Example 2:
* Input:
* s = "aa"
* p = "*"
* Output: true
* Explanation: '*' matches any sequence.
* Example 3:
* Input:
* s = "cb"
* p = "?a"
* Output: false
* Explanation: '?' matches 'c', but the second letter is 'a',
* which does not match 'b'.
* Example 4:
* Input:
* s = "adceb"
* p = "*a*b"
* Output: true
* Explanation: The first '*' matches the empty sequence,
* while the second '*' matches the substring "dce".
* Example 5:
* Input:
* s = "acdcb"
* p = "a*c?b"
* Output: false2. 사고 분석
* ：
* 1： ，dp[lp+1][ls+1]; dp[lp][ls]
* dp[i][j] p i s j ；
* '*' 0 1 ：
* ① 0 ：dp[i][j]=dp[i-1][j];
* ② 1 ( '?')：dp[i][j]=dp[i-1][j-1];
* ③ ：dp[i][j]=dp[i-1][j-2]||dp[i-1][j-3]||...||dp[i-1][0];
* ， ：dp[i][j]=dp[i-1][j]||dp[i-1][j-1]||...||dp[i-1][0];
* ps[i]='*', j-1 j, dp[i][j-1]=dp[i-1][j-2]||...||dp[i-1][0];
* dp[i][j] = dp[i-1][j]||dp[i][j-1]; ps[j]='*';
* ：( )
* dp[i][j] = dp[i-1][j]||dp[i][j-1]; ps[i]=='*';
* dp[i][j] = dp[i-1][j-1]&&(ps[i] == '?' || ss[j] == ps[i]); ps[i]！='*';
* ：dp[i][j] 、 dp ； 。
* 2： ： dp[];
* ， 。3. 자바 코드
(1). 방법 1
/ * * 방법 1: 동적 기획 dp [] [];(가장 이해 하기 쉬 운) * 시간 복잡 도와 공간 복잡 도가 비교적 높 고 O (M * N). * /public boolean isMatch1(String s, String p) { char[] ss = s.toCharArray(), ps = p.toCharArray(); int ls = ss.length, lp = ps.length; boolean[][] dp = new boolean[lp + 1][ls + 1]; dp [0] [0] = true; / 초기 화 for (int i = 1; i <= lp; i++) { if (ps[i - 1] == '*') { dp [i] [0] = dp [i - 1] [0]; / / 경계 문제 (왼쪽 만 위쪽 이 없 음) for (int j = 1; j <= ls; j++) dp [i] [j] = dp [i - 1] [j] | dp [i] [j - 1]; / 위 와 왼쪽 } else { for (int j = 1; j <= ls; j++) dp [i] [j] = (ps [i - 1] = '?' | ss [j - 1] = = ps [i - 1]) & dp [i - 1] [j - 1]; / / 왼쪽 상단 } } return dp[lp][ls]; }
(2). 방법 2
/ * * 방법 2: 동적 계획 dp [2] []; * 2 개의 1 차원 배열 dp []; 공간 복잡 도 감소 O (M * N) - > O (2 * N) * 시간 복잡 도가 약간 높 아 집 니 다. 2 개의 1 차원 배열 간 copy 와 비우 기 작업 은 일정한 대가 입 니 다. * / public boolean isMatch 2 (String s, String p) { if (s! = null & s. equals (p) return true; / 같 으 면 true 로 바로 돌아 갑 니 다. char[] ss = s.toCharArray(), ps = p.toCharArray(); int ls = ss.length, lp = ps.length; boolean [] [] dp = new boolean [2] [ls + 1]; / 2 개의 1 차원 배열 dp [0] [0] = true; / 초기 화 for (int i = 1; i <= lp; i++) { if (ps[i - 1] == '*') { dp [1] [0] = dp [0] [0]; / / 경계 문제 (왼쪽 만 위쪽 이 없 음) for (int j = 1; j <= ls; j++) dp [1] [j] = dp [0] [j] | dp [1] [j - 1]; / 위 와 왼쪽 for (int k = 0; k <= ls; k++) dp[0][k] = dp[1][k]; dp [1] [0] = false; / / 비 웁 니 다. 이 요 소 는 자동 으로 덮어 쓸 수 없 기 때 문 입 니 다. } else { for (int j = 1; j <= ls; j++) dp [1] [j] = (ps [i - 1] = '?' | ss [j - 1] = = ps [i - 1]) & dp [0] [j - 1]; / / 왼쪽 상단 for (int k = 0; k <= ls; k++) dp[0][k] = dp[1][k]; dp [1] [0] = false; / / 비 웁 니 다. 이 요 소 는 자동 으로 덮어 쓸 수 없 기 때 문 입 니 다. } } return dp [0] [ls]; / / 반드시 [0] 으로 돌아 가 특수 사례 를 피하 고 for 순환 에 들 어가 지 않 은 경우}
(3). 방법 3
/ * * 방법 3: 시간 복잡 도의 최적화: 2 차원 dp [] [] 를 바탕 으로 최적화 합 니 다. * 최적화: * (1) pos 와 pos b 를 도입 합 니 다. * A, int pos 는 현재 줄 의 첫 번 째 일치 점, 즉 i 줄 에서 dp [i] [j] 를 표시 합 니 다.첫 번 째 는 true 의 j 값 입 니 다. * B, boolean pos b 는 현재 줄 에 일치 하 는 점 이 있 는 지 표시 합 니 다. 만약 에 한 줄 에 일치 하 는 점 이 존재 하지 않 는 다 면 * 는 뒤에 도 존재 하지 않 고 false 로 돌아 갑 니 다. * (2) pos 의 역할: pos 는 현재 줄 의 첫 번 째 일치 점 이 고 다음 줄 의 일치 점 은 pos 나 pos + 1 이후 에 있 을 것 입 니 다. * 원인: dp [i] [j]왼쪽 위, 왼쪽, 위 세 개의 값 에 따라 결 정 됩 니 다. 따라서 현재 첫 번 째 일치 하 는 점 * 이 나타 나 면 반드시 이전 라운드 의 첫 번 째 일치 점 이후 pos 를 이용 하여 다음 라운드 부터 일치 하 는 위 치 를 기록 합 니 다. * p 의 다음 문 자 는 '*' 이 고 다음 줄 은 pos 부터 시작 합 니 다. pos 이전의 문 자 는 false 입 니 다. * p 의 다음 문 자 는 '*' 가 아니 라 다음 줄 은 pos + 1 위치 에서 직접 열 립 니 다.처음에 pos 와 pos 이전의 것 은 false 였 다. 그 이 유 는 다음 과 같다. * ① p [i] = '*', dp [i] [j] = dp [i - 1] [j] | dp [i] [j - 1]; 위쪽 이나 왼쪽 값 이 true 라면 dp [i] [j] = true; * 그래서 반드시 dp [i] [pos] = dp [i - 1] [pos] = true; dp [i] [pos] = true, * 더 나 아가 dp [i] [pos + 1] = true, dp [2] = true,..., dp [ls]= true; 는 pos 부터 끝까지 true 입 니 다. * ② p [i]! = '*', pos 는 1 을 먼저 추가 해 야 합 니 다. 이때 dp [i] [j] 는 dp [i - 1] [j - 1] 왼쪽 상단 값 과 만 관련 되 고 다음 열 에 있 기 때문에 pos + +. * / public boolean isMatch (String s, String p) { char[] ss = s.toCharArray(); char[] ps = p.toCharArray(); int ls = ss.length, lp = ps.length; boolean[][] dp = new boolean[lp + 1][ls + 1]; dp [0] [0] = true; / 초기 화 boolean pos_b = true; for (int i = 1, pos = 0; i <= lp && pos_b; i++) { if (ps[i - 1] == '*') { for (int j = pos; j < = ls; j + +) dp [i] [j] = true; / pos 부터 ls 까지 모두 true } else { pos_b = false; for (int j = + pos; j < = ls; j + +) {/ / 아니 *, 직접 앞으로; * 일치 하지 않 을 수 있 으 므 로 지금부터 시작 합 니 다. dp[i][j] = dp[i - 1][j - 1] && (ps[i - 1] == '?' || ss[j - 1] == ps[i - 1]); if (pos b) contine; / 일치 점 이 이미 존재 합 니 다. if (dp [i] [j]) {/ 기억 하고 첫 번 째 것 만 기억 하 는 것 은 true 이 며, 다음 라운드 의 pos 출발점 으로 합 니 다. pos b = true; / 현재 줄 에 일치 하 는 점 이 있 음 을 표시 합 니 다. pos = j; / 현재 줄 의 첫 번 째 일치 점 위치 } else pos +; / / 여 기 는 없 을 수 있 고 없 애 도 완전히 통과 할 수 있 습 니 다. 목적 은 일치 하 는 점 을 찾 지 못 할 때 pos 도 전진 하 는 것 입 니 다. } } } print(dp); return dp[lp][ls]; }
(4). 방법 4
/ * * 방법 4: 더 최적화 합 니 다. 1 차원 dp [] 에서 최적화 합 니 다. * 가장 좋 은 방법 일 것 입 니 다. * / public boolean isMatch 1 P (String s, String p) { if (s! = null & s. equals (p) return true; / 같 으 면 true 로 바로 돌아 갑 니 다. char[] ss = s.toCharArray(), ps = p.toCharArray(); int ls = ss.length, lp = ps.length; boolean [] [] dp = new boolean [2] [ls + 1]; / 2 개의 1 차원 배열 dp [0] [0] = true; / 초기 화 boolean pos_b = true; for (int i = 1, pos = 0; i <= lp && pos_b; i++) { if (ps[i - 1] == '*') { for (int j = pos; j <= ls; j++) dp[1][j] = true; for (int k = 0; k <= ls; k++) { dp[0][k] = dp[1][k]; dp [1] [k] = false; / / 비 웁 니 다. 두 번 째 부터 옮 겨 다 니 는 것 이 아니 기 때문에 모두 비 워 야 합 니 다. false 입 니 다. } } else { pos_b = false; for (int j = ++pos; j <= ls; j++) { dp [1] [j] = (ps [i - 1] = '?' | ss [j - 1] = = ps [i - 1]) & dp [0] [j - 1]; / / 왼쪽 상단 if (pos_b) continue; if (dp[1][j]) { pos_b = true; pos = j; } else pos++; } for (int k = 0; k <= ls; k++) { dp[0][k] = dp[1][k]; dp [1] [k] = false; / / 비 웁 니 다. 두 번 째 부터 옮 겨 다 니 는 것 이 아니 기 때문에 모두 비 워 야 합 니 다. false 입 니 다. } }
/ / 보조: 출력 2 차원 배열 public void print (boolean [] [] arr) {Arrays. stream (arr). foreach (a - > System. out. println (Arrays. toString (a)))); System. out. println ("= = = = = = = = = = = = = = = = = = = = = = =");}
} return dp [0] [ls]; / / 반드시 [0] 으로 돌아 가 특수 사례 를 피하 고 for 순환 에 들 어가 지 않 은 경우}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
