[LeetCode] Scramble String(일반적이지 않은 DP 해결)
'.' and '*' . '.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true이 문제의 귀착적인 사고방식은 매우 뚜렷하고 대체적인 사고방식은 다음과 같다.
s1과 s2에 대해 각각 두 개의 하위 문자열로 나뉜다.각각 s1 라고 부른다left, s1_right, s2_left, s2right.만약 s1과 s2가 scramble라면 두 가지 상황만 있을 뿐이다.
1) s1_left와 s2left는 scramble이고 s1left와 s2left는 scramble입니다.
2) s1_left와 s2right는 scramble이고 s1right 및 s2left는 scramble입니다.
여기에 귀속되면 하위 문제를 반복해서 풀 수 있다는 점을 감안하면 DP를 사용할 수밖에 없다.일반적인 DP 방법을 사용하려면 3차원 DP가 필요합니다: dp[i][j][k]는 s1이 i에서 시작하고 s2가 j에서 시작하며 길이가 k인 두 개의 하위 문자열이 scramble인지 여부를 나타냅니다.
그러나 상기 해법은 매우 번거롭고 사실 이런 3차원 DP표에는 여전히 불필요한 상태가 저장되어 있다.스스로 비상식적인 DP 구해 방법을 생각해 냈는데, 3차원 DP 시계를 해시 시계로 대체하여 불필요한 상태에 대한 저장을 줄일 수 있다는 것을 발견하였다.그리고 이곳의 DP는 사실상 귀착적인 사고방식과 같이 자정향하는 것이지 이른바 진정한 자저상향의 DP가 아니다.
여기에 하위 문제의 해답 결과를 기록하는 데이터 구조는Map
또한 두 문자열의 길이가 같지 않으면 바로false로 되돌아갈 수 있는 몇 개의 빠른 귀속 출구를 제공합니다.다른 하나는 두 문자열의 내용이 같으면true로 바로 되돌아갈 수 있다는 것이다.
// Memo for dp.
private Map<String, Boolean> dp = new HashMap<String, Boolean>();
public boolean isScramble(String s1, String s2) {
String key = s1 + "@" + s2;
if (dp.containsKey(key)) {
return dp.get(key);
}
// Two quick recursion exits.
if (s1.length() != s2.length()) {
dp.put(key, false);
return false;
}
if (s1.equals(s2)) {
dp.put(key, true);
return true;
}
// Partition and match recursively.
for (int i = 1; i < s1.length(); ++i) {
for (int j = 1; j < s2.length(); ++j) {
// i and j are the partition indexes.
String s1_left = s1.substring(0, i);
String s1_right = s1.substring(i);
String s2_left = s2.substring(0, j);
String s2_right = s2.substring(j);
if (isScramble2(s1_left, s2_right)
&& isScramble2(s1_right, s2_left)
|| isScramble2(s1_left, s2_left)
&& isScramble2(s1_right, s2_right)) {
return true;
}
}
}
dp.put(key, false);
return false;
}사실 이 문제는 DP 외에도 사용할 수 있다
귀속+가지치기 방법.간단한 귀환은 TLE를 초래하지만, 효과적인 가지치기는 때로DP보다 더 좋은 효과를 얻을 수 있다.
이곳의 가지치기 조건은 괜찮다
간단하게 설정하면 모든 문자의 ASCII 값의 합은 반드시 같아야 한다. 이것은 scramble의 충분한 조건이 된다.코드는 다음과 같다.
public boolean isScramble2(String s1, String s2) {
// Two quick recursion exits.
if (s1.length() != s2.length())
return false;
if (s1.equals(s2))
return true;
// Prune candidates here to reduce candidate check times.
int sum = 0;
for (int i = 0; i < s1.length(); i++) {
sum += s1.charAt(i) - 'a';
sum -= s2.charAt(i) - 'a';
}
if (sum != 0)
return false;
// Partition and match recursively.
for (int i = 1; i < s1.length(); ++i) {
for (int j = 1; j < s2.length(); ++j) {
// i and j are the partition indexes.
String s1_left = s1.substring(0, i);
String s1_right = s1.substring(i);
String s2_left = s2.substring(0, j);
String s2_right = s2.substring(j);
if (isScramble2(s1_left, s2_right)
&& isScramble2(s1_right, s2_left)
|| isScramble2(s1_left, s2_left)
&& isScramble2(s1_right, s2_right)) {
return true;
}
}
}
return false;
}이 문제를 총괄해 보자.일반적으로 가장 좋은 문제를 구하는 데는 일반적으로 두 가지 사고방식이 있다.
1) 충분한 행운으로 탐욕성을 발견할 수 있다면 탐욕법을 우선선택해야 한다.(이 문제는 분명 욕심이 없어서 소홀히 할 수 있다.)
2) 그렇지 않으면 귀속 성질을 찾아 귀속 구해를 시도한다.
2) 여기서 먼저 하위 문제가 반복적으로 풀릴지 여부를 본다.만약 중복된 하위 문제 구해가 존재한다면 사실 세 가지 선택이 있을 수 있다.
1) DP는 일반적인 사고방식이다.
2)귀속+가지치기(당연히DP를 사용할 때도 가지치기가 가능함).
3) DP와 귀속 결합: 위에서 아래로 귀속 구해를 구하는 김에 비망록에 부딪힌 하위 문제의 결과를 기록한다.
이 문제는 운행 시간을 보면 귀속+가지치기의 효과가 가장 좋은 것을 발견했다. 주로 이 문제의 귀속 정도가 너무 깊다는 것이다...
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
