[LeetCode] 14. Longest Common Prefix (C#)

LeetCode - Problems - Algorithms - 14. Longest Common Prefix

Problem Description

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:

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

My Solution (C#)

public class Solution {
    public string LongestCommonPrefix(string[] strs)
    {
        if (strs.Length == 0)
        {
            return "";
        }

        string temp;
        for (int i = 0; i < strs[0].Length; i++)
        {
            temp = strs[0].Substring(i, 1);

            for (int j = 1; j < strs.Length; j++)
            {
                if (strs[j].Length == i || temp != strs[j].Substring(i, 1))
                {
                    return strs[0].Substring(0, i);
                }
            }
        }
        return strs[0];
    }
}

주어진 string array 요소들의 공통 접두사를 찾는 문제이다.

string array를 위한 반복문과, 각 단어의 letter들을 확인하기 위한 반복문 두 개가 필요하다.

보통 이런 비교를 하게 되면 array index를 위한 반복문 안에 array 요소 내의 index를 위한 반복문을 만드는 경우가 많은데, 이 경우에는 반대로 하는 것이 훨씬 간단하고 편리하다.

 

우선은 strs array에 요소가 없는 경우를 if 문을 이용해 가장 먼저 걸러준다.

 

이후 비교를 위한 임시 string 값, temp를 만들어주었고 이중 반복문을 시작했다.

모든 array 요소의 공통 접두사를 찾는 것이기 때문에 간단하게 제일 첫 요소를 기준으로 letter를 참고할 for 반복문을 만들었다. 이 때 temp에 비교할 문자를 대입한다.

 

그 안에 strs array의 모든 요소를 확인 하는 내부 반복문을 만들어준다.

(strs array의 첫번째 요소의 letter는 이미 temp에 대입했으므로 index 값인 j는 1부터 시작한다.)

외부 반복문의 i값 (비교 letter의 index 값)을 이용해 모든 요소들의 i 위치에 해당하는 letter들을 비교해준다.

 

비교하기 전에 주의해야할 점: 우리는 strs의 첫번째 요소를 기준으로 비교하고 있다.

다른 요소들의 길이가 strs[0]보다 짧은 경우, ArgumentOutOfRangeException이 발생한다.

따라서 letter를 비교하기 전에 비교할 단어의 길이가 i와 같은지 확인을 먼저 해줘야한다.

|| (or) 연산자의 경우 왼쪽 값이 True일 경우 오른쪽 값을 체크하지 않기 때문에 반드시 왼쪽에 strs[j].Length == i를 작성해야한다.

 

이중 반복문 내부의 if 문에서 가장 짧은 길이의 단어의 letter 갯수만큼 확인이 끝났거나, 혹은 같은 index 값의 letter 값들이 다른 것이 확인돌 경우 strs[0]의 0부터 i까지의 값을 Substring을 이용해 return 한다.

이중 반복문이 끝날때까지 아무런 값이 return 되지 않은 경우, strs array의 첫번째 요소가 가장 짧은 단어인 것이고, 그 외의 모든 요소들이 첫번째 단어를 접두사로서 포함하고 있다는 의미이므로 첫번째 요소를 그대로 return 하면 된다.

 

LeetCode - 14. Longest Common Prefix