LeetCode 65 Scramble String

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
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;
    }
}

좋은 웹페이지 즐겨찾기