14. 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: ["flower","flow","flight"] Output: "fl"

Example 2:

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

Note:

All given inputs are in lowercase letters a-z.

 

번역

 

모든 주어진 문자열 배열을 통틀어서 가장 긴 접두사를 구하라. 만약 공통된 접두사가 없으면 ""를 반환해라
예 1 :

입력 : [ "flower", "flow", "flight"]

출력 : "fl"

예 2 :

입력 : [ "dog", "racecar", "car"]

출력 : "" 설명 : 입력 문자열 사이에 공통 접 두부가 없습니다. 노트 : 주어진 모든 입력은 소문자 a-z입니다.

 

다른 사람의 풀이

1

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

 

2

간단한 문제다. 각 문자열의 문자를 가르키는 공통된 인덱스 변수를 두고 그 변수를 따라서 공통 접두사를 구하면 된다.

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size() == 0)
            return "";
 
        int loc=0;
        int minSize = 9999999;
        for(string s : strs){
            minSize = std::min(minSize, (int)s.size());
        }
 
        string ret="";
        bool flag = true;
        for(int i=0; i<minSize; ++i){
            char currentChar = strs[0][i];
            flag = true;
            for(int j=0; j<strs.size(); ++j){
                if(currentChar != strs[j][i]){
                    flag = false;
                    break;
                }
            }
            if(!flag)
                break;
            ret += strs[0][i];
        }
         
        return ret;
    }
};

 

풀이

 

출처 sources

• https://leetcode.com/problems/longest-common-prefix/

Longest Common Prefix - LeetCode

https://engkimbs.tistory.com/652

[LeetCode, 리트코드] Longest Common Prefix

https://engkimbs.tistory.com/652