leetcode hard : K-Similar Strings

https://leetcode.com/problems/k-similar-strings/description/

K-Similar Strings - LeetCode

 

K-Similar Strings

풀기 전

꽤나 막막한거같다. 일단 상수조건에서 문자열의 길이가 꽤나 짧고 포함하는 English letters set 풀도 그렇게 넓지 않은 걸 보니 Backtracking을 살짝 의심할 수도 있을 것 같다.

처음에 보자마자 든 생각은.. 일단 s1과 s2는 anagram이니까 길이는 같을 것이다. 당연히 각 알파벳의 수도 세어보면 둘이 같아야 된다. s1과 s2가 주어졌을 때 일부 글자들은 이미 맞을수도 있다. 예를 들어

s1 = ‘abcdef’

s2 = ‘bacdef’

‘cdef’부분은 이미 맞는다. 그럼 이 맞는 부분은 건들 필요 없는거 아닐까? 꼭 연속적일 필요도 없다.

s1 = ‘abcdef’

s2 = ‘adcbef’

‘acef’부분이 이미 맞는다. 그럼 둘이 다른 부분인 ‘bd’와 ‘db’에 대해서만 re-arrange를 진행하면 되지 않을까 싶은거다.

근데 내가 잘못 생각하는거일까 조금 불안하긴 하다. 다른 부분에 대해서만 리어레인지 한다고 하기엔 상수조건이 너무나 작은거같아서..

일단 예시로 직접 문제를 한번 풀어보자

s1 = ‘abcd’

s2 = ‘dcba’

맞는 게 하나도 없는 경우다.

이 경우 a랑 d를 스왑해주고 b랑 c를 스왑해주면 2번만에 s2랑 똑같이 맞출 수 있다.

하나만 더 풀어보자.

s1 = ‘abcde’

s2 = ‘bcdea’

이번에도 역시 맞는게 하나도 없다.

s2의 맨 앞글자부터 보면서 swap을 진행한다.

‘abcde’ → ‘bacde’

‘bacde’ → ‘bcade’

‘bcade’ → ‘bcdae’

‘bcdae’ → ‘bcdea’

4번만 에 맞췄다.

s2의 앞글자부터 보면서 맞춰나가면 안되는걸까? 사실 그게 정답이라고 하기엔 상수조건이 터무니없이 작긴하다.

코드 설명

(실패)

솔루션 학습

public int kSimilarity(String A, String B) {

        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.offer(A);
        visited.add(A);
        int level = 0;

        while (!queue.isEmpty()) {
            int sz = queue.size();
            for (int i = 0; i < sz; i++) {
                String curNode = queue.poll();
                if (curNode.equals(B)) {
                    return level;
                }
                for (String neighbour : getNeighbours(curNode, B)) {
                    if (!visited.contains(neighbour)) {
                        queue.offer(neighbour);
                        visited.add(neighbour);
                    }
                }
            }
            level++;
        }

        return -1;
    }
    
    private List<String> getNeighbours(String S, String B) { 
        
        List<String> result = new ArrayList<>();
        char[] arr = S.toCharArray(); 
        
        int i = 0;
        for (; i < arr.length; i++) {
            if (arr[i] != B.charAt(i)) {
                break;
            }
        }
                
        for (int j = i + 1; j < arr.length; j++) { 
            if (arr[j] == B.charAt(i)) {
                swap(arr, i, j);             
                result.add(new String(arr));
                swap(arr, i, j);
            }
        }     
        
        return result;
    }
    
    private void swap(char[] arr, int i, int j) {
        
        char tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

string A랑 B가 있을 때 A에서 swap을 한 번 해서 B랑 최소 글자 하나 이상 맞출 수 있는 경우의 수를 모두 나열해놓고 이를 graph의 children으로 취급해서 BFS를 진행한다. 이미 방문한 string은 같은 children을 만들 것이므로 다시 방문하지 않는다.

Time Complexity는 neighbor가 한번 만들어질때 N개에 비례해서 만들어질 수 있어서 Exponential하지 않을까 추측하는데.. 잘은 모르겠다.