[Sorting and Searching] interview questions #2

[rygh4775]

Group Anagrams: Write a method to sort an array of strings so that all the anagrams are next to each other.

[tgi01054]

솔류션 1

정렬 이용 문자열 배열을 sort 시키고 comparator에서 같은 anagram 끼리는 같은 순서으로 유지 시킵니다.

class AnagramComparator implements Comparator<String>{

    public String sort(String s1){
        char[] chars = s1.toCharArray();
        Arrays.sort(chars);
        return String.valueOf(chars);
    }

    public int compare(String s1, String s2){
        String ss1 = sort(s1);
        String ss2 = sort(s2);        
        return ss1.compare(ss2);
    }
}

String[] array = {"acre", "race", "care", ... , "zoo" };

Arrays.sort( array, new AnagramComparator());

시간 복잡도

N: array 문자열 배열안의 word 갯수 AL(Average Length): 각 word의 평균 크기

word sort 비용 comparator 수행시 sort 비용 ( Nlog(N) ) ( AL log(AL) ) = O( N AL log(N) * log(AL) )

솔류션 2

Hash table 이용해서 같은 anagram 을 같은 slot 또는 bucket에 모읍니다. 그리고 hash table을 iterate 하면서 같은 anagram 을 출력 array에 인접시키면서 구성합니다.

public String sort(String s1){
    char[] chars = s1.toCharArray();
    Arrays.sort(chars);
    return String.valueOf(chars);
}

void arrange(String[] array){

    /* Setup hash table */
    Map<String,List<String>> hashMap = new HashMap<>();
    for(String s: array){
        String sortS = sort(s);
        if( hashMap.contains(sortS)){
            hashMap.get(s).add(s);
        }else{
            hashMap.put(sortS, Arrays.asList(s));
        }
    }

    /* Setup output array */
    int idx = 0;
    for(String s: hashMap.keySet()){
        for(String word: hashMap.get(s)){
            array[idx++] = word;
        }
    }
}

시간 복잡도

N: array 문자열 배열안의 word 갯수

Best case: hashing conflict 발생 X

해쉬 테이블 setup 비용 + 출력 테이블 생성 비용 N AL log(AL) + N = O( N AL log(AL) )

Worst case: 모든 word에 대해서 hashing conflict 발생 O

N N AL log(AL) + N N

• N >> AL 경우: O(N*N)
• N << AL 경우: O(N N AL * log(AL)