LeetCode 65 Scramble String
Below is one possible representation of s1 = "great":
great
/ \
gr eat
/ \ / \
g r e at
/ \
a t
For example, if we choose the node "gr"and swap its two children, it produces a scrambled string "rgeat". rgeat
/ \
rg eat
/ \ / \
r g e at
/ \
a t
We say that "rgeat"is a scrambled string of "great". Similarly, if we continue to swap the children of nodes "eat"and "at", it produces a scrambled string "rgtae".
rgtae
/ \
rg tae
/ \ / \
r g ta e
/ \
t a
We say that "rgtae"is a scrambled string of "great". Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
분석:
인터넷에 게이지의 해법이 있는데 해석을 봐도 알 수 있다. 단지 나는 내가 이 문제를 보았기 때문에 게이지로 할 생각을 할 수 없다고 생각해서 나는 자신의 귀속 코드를 붙였다.
제목이 문자열을 두 갈래 나무의 형식으로 표시한 이상 나는 당연히 먼저 돌아가는 것을 생각했다.
s1을 s11과 s12, s2를 s21과 s22로 나누면
isScramble(s11, s21) && isScramble(s12, s22)
혹은
isScramble(s11, s22) && isScramble(s12, s21)
어떻게 분할하는지 우리는 모른다. 그래서 모든 위치를 시험해야 한다. 한 위치의 분할이 가능하다면true로 돌아갈 수 있다.
귀속 해법에 대해 말하자면 가지를 잘라야만 지나갈 수 있다. 가지를 자르는 것은 불합리한 것을 가능한 한 빨리 제거하고 다시는 귀속에 들어가지 말라는 뜻이다.
예:
1, 길이가 같지 않음,
2, 정렬 후 내용이 다르다
그리고 가능한 한 빨리 결과를 얻을 수 있는
s1.equals(s2)
이것도 하층부에 들어가 귀속할 필요가 없다.
또한 적용 가능한 상황에서 통 배열이 가장 빠른 순서라는 것을 우리는 알고 있다.
public class Solution {
public boolean isScramble(String s1, String s2) {
if(s1.length() != s2.length()) return false;
if(s1.equals(s2)) return true;
int[] count = new int[26];
int len = s1.length();
for(int i=0; i<len; i++){
count[s1.charAt(i)-'a']++;
count[s2.charAt(i)-'a']--;
}
for(int i=0; i<26; i++){
if(count[i]!=0) return false;
}
for(int step=1; step<len; step++){
String s11 = s1.substring(0,step);
String s12 = s1.substring(step);
String s21 = s2.substring(0,step);
String s22 = s2.substring(step);
if(isScramble(s11,s21)&&isScramble(s12,s22)) return true;
s21 = s2.substring(0, len-step);
s22 = s2.substring(len-step);
if(isScramble(s11,s22)&&isScramble(s12,s21)) return true;
}
return false;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.