Scramble String - LeetCode

Problem

1. input: 길이가 같은 문자열 s1, s2
2. output: s1을 아래의 방법으로 조작하여 s2로 만들 수 있는지 여부 리턴
   • Split the string into two non-empty substrings at a random index, i.e., if the string is s, divide it to x and y where s = x + y.
   • Randomly decide to swap the two substrings or to keep them in the same order. i.e., after this step, s may become s = x + y or s = y + x.
   • Apply step 1 recursively on each of the two substrings x and y.

• s1.length == s2.length
• 1 <= s1.length <= 30
• s1 and s2 consist of lowercase English letters.

Idea

전체를 부분으로 나누고 그 과정에서 타겟값이 존재하는지 확인하는 전형적인 DP(Memoizatoin)문제 → Sol1

하지만 점수가 그다지 좋지 않아서, 다른 답을 참고하던 중, 애초에 문자열의 문자구성이 달라서 답이 될 수 없는 경우를 처리하는 것이 시간을 많이 줄이는 것을 발견 하였다 → Sol2

Solution

1. DP(Memoization)

   문자열을 x, y로 나누고 s1-s2 를 키값으로 DP map에 저장

   class Solution {
       val dp = mutableMapOf<String, Boolean>()
       fun isScramble(s1: String, s2: String): Boolean {
           if (s1 == s2) return true
           if (dp.containsKey("$s1-$s2")) return dp["$s1-$s2"]!!
           val n = s1.length
           for (i in 1 until n) {
   						// x = x' & y = y'  Or x = y' & y = x'
               if ((isScramble(s1.substring(0,i), s2.substring(0,i)) && isScramble(s1.substring(i,n), s2.substring(i,n))) || (isScramble(s1.substring(0,i), s2.substring(n-i,n)) && isScramble(s1.substring(i,n), s2.substring(0,n-i)))) {
                   dp["$s1-$s2"] = true
                   return true
               }
           }
           dp["$s1-$s2"] = false
           return false
       }
   }
   

   

2. 1의 방식에서 답이 될 수 없는 경우 미리 체크

   두 문자열의 문자구성이 다른 경우 체크

   class Solution {
       val dp = mutableMapOf<String, Boolean>()
       fun isScramble(s1: String, s2: String): Boolean {
           if (s1 == s2) return true
           val cntCheck = hashMapOf<Char, Int>()
   				// 이미 문자 구성이 다른경우 체크
           for (c in s1) {
               cntCheck[c] = cntCheck.getOrDefault(c, 0) + 1
           }
           for (c in s2) {
               if (cntCheck[c] == null || cntCheck[c] == 0) return false
               cntCheck[c] = cntCheck[c]!! - 1
           }
           if (dp.containsKey("$s1-$s2")) return dp["$s1-$s2"]!!
           val n = s1.length
           for (i in 1 until n) {
   						// x = x' & y = y'  Or x = y' & y = x'
               if ((isScramble(s1.substring(0,i), s2.substring(0,i)) && isScramble(s1.substring(i,n), s2.substring(i,n))) || (isScramble(s1.substring(0,i), s2.substring(n-i,n)) && isScramble(s1.substring(i,n), s2.substring(0,n-i)))) {
                   dp["$s1-$s2"] = true
                   return true
               }
           }
           dp["$s1-$s2"] = false
           return false
       }
   }
   

   

Point

1. DP(Memoization)