[LeetCode] 1460. Make Two Arrays Equal by Reversing Sub-arrays

Given two integer arrays of equal length target and arr.

In one step, you can select any non-empty sub-array of arr and reverse it. You are allowed to make any number of steps.

Return True if you can make arr equal to target, or False otherwise.

 

Example 1:

Input: target = [1,2,3,4], arr = [2,4,1,3] Output: true Explanation: You can follow the next steps to convert arr to target: 1- Reverse sub-array [2,4,1], arr becomes [1,4,2,3] 2- Reverse sub-array [4,2], arr becomes [1,2,4,3] 3- Reverse sub-array [4,3], arr becomes [1,2,3,4] There are multiple ways to convert arr to target, this is not the only way to do so.

Example 2:

Input: target = [7], arr = [7] Output: true Explanation: arr is equal to target without any reverses.

Example 3:

Input: target = [1,12], arr = [12,1] Output: true

 

Constraints:

• target.length == arr.length
• 1 <= target.length <= 1000
• 1 <= target[i] <= 1000
• 1 <= arr[i] <= 1000

 

### Solution

class Solution:
    def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
        zero = [0 for i in range(len(target))]
        A = {k:v for k,v in zip(target,zero)}
        for k in target:
            A[k] += 1

        zero2 = [0 for i in range(len(arr))]
        B = {k:v for k,v in zip(arr,zero2)}
        for k in arr:
            B[k] += 1
        
        if A == B:
            return True 
        else:
            return False

#memo 

 

문제를 풀다가 발견한 패턴인데.. 주어진 arr 어레이의 요소들이 t , t+1 순서로 무한히 자리바꿈이 가능하다면.. 

어떠한 형태의 어레이로도 변형 가능하다. 단, 각 요소들의 개수만 같다면. 그래서 각 array 들을 dict 형태로 

바꾸고 요소값들을 카운팅해주는 형태로 바꾸었다. 다른 두 어레이의 counting dict 이 일치한다면 true 를 리턴해준다.