Longest Common Prefix

주어진 문자열 배열의 최대 길이의 동일 prefix 를 찾는 문제이다.
로드맵상 Trie 문제로 열심히 풀었으나... 사실 단순히 String 클래스의 startsWith 메서드를 쓰는게 더 편하다는 사실을 후에 알았다.

 

그럼에도 일단 문제를 통과했으니 해결한 코드를 소개한다.
Trie 구조에 repeat이란 int 값을 추가해주었다. 저장되는 문자들의 동일한 문자가 반복 저장되는 부분을 추가해준 것이다. 따라서 repeat 값을 보면 해당 문자까지 동일한 prefix를 갖는 문자열의 개수를 알 수 있다. 아래는 완성코드이다.

public class Solution {  
    public String longestCommonPrefix(String[] strs) {  
        Trie root = new Trie();  
        for(String str: strs){  
            Trie head = root;  
            char[] c = str.toCharArray();  
            for(int i = 0; i < c.length; i++){  
                int check = c[i] - 'a';  
                if(head.next[check] == null){  
                    head.next[check] = new Trie();  
                }else{  
                    head.next[check].repeat++;  
                }  
                head = head.next[check];  
            }  
        }  
  
        StringBuilder sb = new StringBuilder();  
        Trie head = root;  
        while(head != null){  
            Trie[] next = head.next;  
            boolean isExist = false;  
            for(int i = 0; i < next.length; i++){  
                if(next[i] != null && next[i].repeat == strs.length){  
                    isExist = true;  
                    sb.append(Character.toString(i + 'a'));  
                    head = next[i];  
                    break;  
                }  
            }  
  
            if(!isExist) break;  
        }  
  
        return sb.toString();  
    }  
  
    private static class Trie{  
        Trie[] next;  
        int repeat;  
  
        Trie(){  
            next = new Trie[26];  
            repeat = 1;  
        }  
    }  
}