[LeetCode - C] 14. Longest Common Prefix

Longest Common Prefix - LeetCode

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

 

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

 

Constraints:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lower-case English letters.

---

Solution 1

 

처음에는 strs[0]을 저장하고 strs[1]부터 prefix 비교하여

 

새로운 char *만들어 동적할당하고 free를 반복하는 방법으로

 

마지막에 생성된 char *을 리턴하는 방식으로 해결하려 했다.

 

malloc free 관리가 아직 익숙하지 않아 컴파일이 되지 않아

 

그냥 min 찾는 방식을 이용해 prefix의 길이를 구한 뒤

 

strs[0][r_idx]에 '\0'을 넣는 방식을 사용했다.

(C에서는 str을 char *의 '\0'을 넣어 만듦)

char * longestCommonPrefix(char ** strs, int strsSize)
{
    char    *ret;
    char    *temp;
    int     idx;
    int     c_idx;
    int     r_idx;
    
    idx = 0;
    temp = strs[idx];
    r_idx = strlen(strs[idx]);
    while (++idx < strsSize)  
    {
        c_idx = 0;
        while (strs[idx][c_idx] && temp[c_idx] && strs[idx][c_idx] == temp[c_idx])
            c_idx++;
        if (r_idx > c_idx)
            r_idx = c_idx;
    }
    temp[r_idx] = '\0';
    return (temp);
}

---

Solution 2

(leetcode 제공)

 

JAVA에서 제공하는 indexOf, substring 이용해서 해결하는 방법

 

prefix에 strs[0]을 저장해 두고 strs[i].indexOf를 이용하여

 

prefix가 존재하나 찾아보는 방법이다.

 

만약 없다면 substring 이용하여 맨 뒤의 문자를 하나씩 제거한다.

 public String longestCommonPrefix(String[] strs)
 {
    if (strs.length == 0) return "";
    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 "";
        }        
    return prefix;
}

---

Solution 3

(leetcode 제공)

 

JAVA에서 제공하는 charAt, substring 이용해서 해결하는 방법

 

c에 strs[0]의 i번째 char을 저장한 뒤

 

strs[j]의 i번째 char이 c와 일치하는지 보는 방법이다.

 

같지 않거나 strs[0]과 strs[j]의 길이가 같다면 substring하여 return한다.

 

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];
}

---

Solution 4

(leetcode 제공)

 

재귀를 활용한 방법

 

재귀가 아직 익숙지 않아 코드를 이해하는데 좀 걸렸다

 

만약 4개의 strs가 들어오면

 

l, r이 각각 0과 3으로 longestCommonPrefix에 매개변수를 넘긴다.

 

이후 lcpLeft, lcpRight에서 재귀 호출하는데

 

mid의 값이 1이 되므로 0,1과 2,3으로 쪼개지고

 

이후 0,1은 0,0과 1,1로 2,3은 2,2와 3,3으로 재귀 호출하므로

 

각각 strs[l]을 리턴하게 되는데 여기서 리턴 받은 strs를

 

commonPrefix에서 Math.min으로 

 

둘 중 길이가 작은 문자열의 길이를 구해

 

charAt을 이용하여  prefix를 구한다.

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);
}

---

Solution 5

(leetcode 제공)

 

startsWith을 이용한 풀이

 

startsWith을 처음 봐서 찾아보니

 

문자열이 인수로 시작하는지 여부를 bool로 return 한다고 한다.

 

prefix의 경우 strs[]에서 가장 짧은 길이를 가진 문자열보다

 

길이가 길 수 없으니 strs[]에서 가장 짧은 문자열의 길이를 구한다.

 

이후 middle값을 구해 문자열의 절반을 prefix라 가정 후

 

startsWith을 통해 strs속 모든 문자열에 포함되어 있는지 확인한다.

 

결과에 따라 low을 증가시키거나 high을 감소시켜 middle 값을 조정하고

 

low와 high가 같아지게 된다면 prefix를 만족하는 문자열을 구한 것 이기에

 

substring 하여 prefix를 리턴한다.

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;
}

---

Solution 6

(leetcode 제공)

 

trie(트라이)를 이용한 방법

 

아직 trie가 뭔지 몰라서 공부하고 재작성해야겠다.

 

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 
{
    private TrieNode[] links;
    private final int R = 26;
    private boolean isEnd;
    private int size;   
    
    public void put(char ch, TrieNode node) 
    {
        links[ch -'a'] = node;
        size++;
    }

    public int getLinks() 
    {
        return size;
    }
}

public class Trie 
{

    private TrieNode root;

    public Trie() 
    {
        root = new TrieNode();
    }

    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();
    }
}