Leetcode - 14. Longest Common Prefix - Easy

오늘의 문제는 스트링 배열 들이 공통으로 가지고 있는 prefix 를 찾는 문제 입니다.

이 문제를 다루려면 우선 String API 중 indexOf() 와 substring() 메소드를 알아야 합니다.

IndexOf()는 원하는 글자가 어떤 스트링 에 몇번째에 있는지 알 수 있는 메소드 입니다. 그 글자가 없으면 -1이 반환됩니다.

Substring()은 해당 스트링의 일부 문자만 가져오고 싶을 때 사용합니다.

 

이 두 메소드를 활용해서 만든  코드는 아래와 같습니다.

 

로직은 우선 첫번째 String과 두번째 String의 prefix부터 먼저 구하고 나머지를 순차적으로 구하는 겁니다.

알아보기 쉽게 하기 위해서 여러곳에 System.out.println()을 넣었습니다.

우선 루프 이전을 살펴보면...

 

class Solution { // 클래스 이름은 Solution

    public String longestCommonPrefix(String[] strs) { // 메소드 이름은 longestCommonPrefix 이고 입력값으로 스트링 배열인 strs를 받고 출력값은 String 이 됩니다.

        String returnValue = ""; // 일단 출력할 String 변수를 생성했습니다. 초기값은 "" 로 했습니다.

        

        if(strs.length == 0) return returnValue; // 입력값이 없으면 "" 를 반환합니다.

        String prefix = strs[0]; // prefix에 입력값의 첫번째 스트링을 넣습니다.

 

일단 입력값은 ["flower","flow","flight", "flown"] 로 가정하겠습니다.

여기서 prefix 는 첫번째 스트링인 flower가 됩니다.

 

이제 루프문을 보겠습니다.

 

for(int i=1; i < strs.length; i++) { // 루프는 입력값의 스트링 숫자만큼 돕니다. 이 경우에는 4번 돕니다.

            System.out.println(i + " prefix is " + prefix); // 위에 설정했듯이 첫번째 루프에서 prefix는 flower 입니다.

            System.out.println(i + " strs is " + strs[i]); // 첫번쨰 루프에서는 strs[1]이니까 두번쨰 스프링인 flow가 그 값이 됩니다.

            while(strs[i]. indexOf(prefix) !=0) { // 이걸 풀면 flow.indexOf(flower)가 되고 flow안에는 flower가 없으니까 -1이 되서 while문을 안으로 들어가게 됩니다.

                prefix = prefix.substring(0, prefix.length() - 1); // prefix가 없으니까 prefix에서 맨 마지막 글자를 뺍니다. 그러면 flower에서 r이 빠져서 prefix는 이제 flowe가 됩니다.

                System.out.println(i + " in while prefix is " + prefix); // prefix가 flowe가 됐으니까 stout에 flow가 출력 됐습니다.

                

                if(prefix.isEmpty()) return returnValue; //prefix가 empty 일 경우 return 하는데 이 경우에는 실행 되지 않습니다.

            }

        }

 

이제 prefix가 flowe가 된 상태에서 다시 시작 합니다.

While 문을 보면 flow.indexOf(flowe)가 되기 때문에 여전히 -1 입니다.

그러면 prefix는 flowe에서 e가 빠진 flow가 됩니다.

그러면 다시 while문을 돌게 되죠.

 

이번에는 flow.indexOf(flow)가 되기 때문에 while문은 0 이 되기 때문에 이 while문을 빠져 나와서 for문을 다시 돌게 됩니다.

 

이제 i 는 ++ 가 되서 2가 됩니다.

그러면 이제 flight을 비교 하게 됩니다.

첫번째 while 문에서는 flow.indexOf(flight) 가 되서 -1 이므로 while 문 안으로 들어가게 됩니다.

그러면 flow에서 w가 빠져서 flo가 됩니다.

While문이 다시 돌게 되고 flo.indexOf(flight)는 -1이므로 prefix는 다시 fl로 바뀝니다.

다음 while문에서는 fl.indexOf(flight)이 0이 되므로 while문을 빠져 나와서 다시 for 문으로 갑니다.

 

이제 i 는 3이 되고 strs[3] 이마로 flown을 비교하게 됩니다.

prefix는 이제 fl입니다.

 

이제 while문에서 fl.indexOf(flight)이 되므로 while문은 그냥 빠져 나오게 됩니다.

그럼 다시 for 문으로 가는데 i 는 4가 되서 strs.length와 같게 되기 때문에 for 문도 빠져 나오게 됩니다.

 

For 문을 빠져 나오면서 아래 코드를 만나게 됩니다.

 

returnValue = prefix; // prefix 가 fl이 됐기 때문에 returnValue에는 이 값이 할당 됩니다.

        return returnValue; // 그 값을 return 합니다.

    }

}

 

이 로직은 이렇게 됩니다.

전체 코드를 다시 보면 이렇습니다.

class Solution {

    public String longestCommonPrefix(String[] strs) {

        String returnValue = "";

        if(strs.length == 0) return returnValue;

        String prefix = strs[0];

        

        for(int i=1; i < strs.length; i++) {

            while(strs[i]. indexOf(prefix) !=0) {

                prefix = prefix.substring(0, prefix.length() - 1);

                if(prefix.isEmpty()) return returnValue;

            }

        }

        

        returnValue = prefix;

        return returnValue;

    }

}

 

이 외에 다른 접근 법으로는 아래와 같은 것들이 있습니다.

 

Approach 2: Vertical scanning

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";
    for (int i = 0; i < strs[0].length() ; i++){
        char c = strs[0].charAt(i);
        for (int j = 1; j < strs.length; j ++) {
            if (i == strs[j].length() || strs[j].charAt(i) != c)
                return strs[0].substring(0, i);             
        }
    }
    return strs[0];
}

 

Strs[0] 은 flower가 됩니다.

for문은 이 flower의 글자 수(6) 만큼 돌리게 됩니다.

우선 char c에는 f가 담기게 되죠. 

두번째 for 문은 입력된 String 갯수 만큼 돕니다.

입력값이  ["flower","flow","flight", "flown"] 이면 두번째 for 문은 4번 돌겠다.

 

If 문에서는 두번째 스트링이 empty거나 empty가 아니더라도 첫번째 글자가 f가 아니면 empty를 반환합니다.

If에 걸리지 않으면 계속 두번째 for 문을 돕니다. 

모든 스트링이 if 문에 걸리지 않았다면 모두 f는 공통으로 가지고 있다는 것이 됩니다.

 

그러면 다시 첫번째 for 문으로 가서 i 가 1이 되고 char c 는 fl이 됩니다.

두번째 for 문이 돌게 되는데 모든 스트링이 다 fl을 가지고 있으므로 두번째 for 문을 빠져 나와서 첫번째 for 문을 다시 돌게 됩니다.

 

이제 i는 2가 되고 char c 는 flo가 됩니다.

이제는 두번째 for 문 안에 있는 if 문에 걸리게 됩니다.

그러면 그 if 문 안에 있는 strs[0].substring(0,i); 이 실행 되게 되고 i는 2 이기 때문에 fl 이 리턴되게 됩니다.

 

다른 방법도 있습니다.

 

Approach 3: Divide and conquer

 

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";    
        return longestCommonPrefix(strs, 0 , strs.length - 1);
}

private String longestCommonPrefix(String[] strs, int l, int r) {
    if (l == r) {
        return strs[l];
    }
    else {
        int mid = (l + r)/2;
        String lcpLeft =   longestCommonPrefix(strs, l , mid);
        String lcpRight =  longestCommonPrefix(strs, mid + 1,r);
        return commonPrefix(lcpLeft, lcpRight);
   }
}

String commonPrefix(String left,String right) {
    int min = Math.min(left.length(), right.length());       
    for (int i = 0; i < min; i++) {
        if ( left.charAt(i) != right.charAt(i) )
            return left.substring(0, i);
    }
    return left.substring(0, min);
}

 

--------------

 

Approach 4: Binary search

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0)
        return "";
    int minLen = Integer.MAX_VALUE;
    for (String str : strs)
        minLen = Math.min(minLen, str.length());
    int low = 1;
    int high = minLen;
    while (low <= high) {
        int middle = (low + high) / 2;
        if (isCommonPrefix(strs, middle))
            low = middle + 1;
        else
            high = middle - 1;
    }
    return strs[0].substring(0, (low + high) / 2);
}

private boolean isCommonPrefix(String[] strs, int len){
    String str1 = strs[0].substring(0,len);
    for (int i = 1; i < strs.length; i++)
        if (!strs[i].startsWith(str1))
            return false;
    return true;
}

 

----------------------------

public String longestCommonPrefix(String q, String[] strs) {

    if (strs == null || strs.length == 0)

         return "";  

    if (strs.length == 1)

         return strs[0];

    Trie trie = new Trie();      

    for (int i = 1; i < strs.length ; i++) {

        trie.insert(strs[i]);

    }

    return trie.searchLongestPrefix(q);

}

 

 

class TrieNode {

 

    // R links to node children

    private TrieNode[] links;

 

    private final int R = 26;

 

    private boolean isEnd;

 

    // number of children non null links

    private int size;    

    public void put(char ch, TrieNode node) {

        links[ch -'a'] = node;

        size++;

    }

 

    public int getLinks() {

        return size;

    }

    //assume methods containsKey, isEnd, get, put are implemented as it is described

   //in  https://leetcode.com/articles/implement-trie-prefix-tree/)

}

 

public class Trie {

 

    private TrieNode root;

 

    public Trie() {

        root = new TrieNode();

    }

 

//assume methods insert, search, searchPrefix are implemented as it is described

//in  https://leetcode.com/articles/implement-trie-prefix-tree/)

    private String searchLongestPrefix(String word) {

        TrieNode node = root;

        StringBuilder prefix = new StringBuilder();

        for (int i = 0; i < word.length(); i++) {

            char curLetter = word.charAt(i);

            if (node.containsKey(curLetter) && (node.getLinks() == 1) && (!node.isEnd())) {

                prefix.append(curLetter);

                node = node.get(curLetter);

            }

            else

                return prefix.toString();

 

         }

         return prefix.toString();

    }

}