C++LeetCode 구현(14.최 장 공통 접두사)

[LeetCode]14.Longest Common 접두사 최 장 공통 접두사
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.
이 문 제 는 일련의 문자열 의 공동 접 두 사 를 구 합 니 다.특별한 기술 이 없습니다.머리 없 이 찾 으 면 됩 니 다.두 개의 변수 i 와 j 를 정의 합 니 다.그 중에서 i 는 검색 문자열 을 옮 겨 다 니 는 문자 이 고 j 는 문자열 을 옮 겨 다 니 는 모든 문자열 입 니 다.여기 서 단 어 를 상하 로 배열 하면 각 줄 의 길이 가 같 지 않 을 수 있 는 2 차원 배열 에 해당 합 니 다.옮 겨 다 니 는 순서 와 일반적인 가로 줄 을 옮 겨 다 니 는 것 이 다 르 고 수직 으로 옮 겨 다 니 는 과정 에서 한 줄 이 없 으 면 가장 짧 은 단어 라 고 설명 합 니 다.공동 접두사 의 길 이 는 가장 짧 은 단어 보다 길 지 않 기 때 문 입 니 다.그래서 이 때 이미 찾 아 낸 공 통 된 접 두 사 를 되 돌려 줍 니 다.첫 번 째 문자열 의 한 위치 에 있 는 단 어 를 꺼 내 고 다른 모든 문자열 의 해당 위 치 를 옮 겨 다 니 며 일치 하 는 지 확인 합 니 다.만족 하지 않 으 면 res 로 돌아 갑 니 다.같 으 면 현재 문 자 를 결과 에 저장 하고 다음 위치 문 자 를 계속 검사 합 니 다.코드 는 다음 과 같 습 니 다.
C++해법 1:

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        string res = "";
        for (int j = 0; j < strs[0].size(); ++j) {
            char c = strs[0][j];
            for (int i = 1; i < strs.size(); ++i) {
                if (j >= strs[i].size() || strs[i][j] != c) {
                    return res;
                }
            }
            res.push_back(c);
        }
        return res;
    }
};

자바 해법 1:

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        String res = new String();
        for (int j = 0; j < strs[0].length(); ++j) {
            char c = strs[0].charAt(j);
            for (int i = 1; i < strs.length; ++i) {
                if (j >= strs[i].length() || strs[i].charAt(j) != c) {
                    return res;
                }
            }
            res += Character.toString(c);
        }
        return res;
    }
}

우 리 는 위의 방법 을 적 절 히 간소화 할 수 있 습 니 다.현재 어떤 문자 와 첫 번 째 문자열 이 대응 하 는 위치 에 있 는 문자 가 같 지 않 은 것 을 발견 하면 더 이상 공동 접두사 가 없 을 것 입 니 다.substr 의 방법 으로 공동 접두사 의 하위 문자열 을 직접 꺼 낼 수 있 습 니 다.옮 겨 다 니 기 전에 결 과 를 되 돌려 주지 않 으 면 첫 번 째 단 어 는 공공 접두사 이 고 결과 로 돌아 가면 된다 는 뜻 이다.코드 는 다음 과 같 습 니 다:
C++해법 2:

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        for (int j = 0; j < strs[0].size(); ++j) {
            for (int i = 0; i < strs.size(); ++i) {
                if (j >= strs[i].size() || strs[i][j] != strs[0][j]) {
                    return strs[i].substr(0, j);
                }
            }
        }
        return strs[0];
    }
};

자바 해법 2:

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

우 리 는 다시 한 가지 해법 을 살 펴 보 자.이런 방법 은 입력 문자열 배열 에 순 서 를 정 해 주 었 는데,이렇게 하면 무슨 좋 은 점 이 있 는 지 생각해 보 자.알파벳 순 으로 정렬 된 이상 공통 자모 가 많은 두 문자열 이 함께 배열 되 고,여러분 과 같은 자모 가 적은 문자열 일수 록 앞 뒤 양쪽 으로 밀 려 나 기 때문에 공통 접두사 가 있 으 면 앞 뒤 양쪽 문자열 에 반드시 나타 나 기 때문에 앞 뒤 알파벳 문자열 의 공통 접두사 만 찾 으 면 됩 니 다.예 를 들 어 예 1 정렬 후[flight],"flow","flower"],예 2 정렬 후[cat","dog","racecar"]로 예 2 는 공동 접두사 가 없 지만 공동 접 두 사 는 빈 문자열 이 고 수미 양쪽 문자열 에 나타난다 고 볼 수 있다.길이 가 아 닌 알파벳 순 으로 배열 되 어 있 기 때문에 이니셜 의 길이 관 계 는 모 르 겠 습 니 다.넘 치 는 오 류 를 방지 하기 위해 서 는 짧 은 것 만 옮 겨 다 니 며 공동 접 두 사 를 찾 아 돌아 오 면 됩 니 다.코드 는 다음 과 같 습 니 다.
C++해법 3:

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        sort(strs.begin(), strs.end());
        int i = 0, len = min(strs[0].size(), strs.back().size());
        while (i < len && strs[0][i] == strs.back()[i]) ++i;
        return strs[0].substr(0, i);
    }
};

자바 해법 3:

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        Arrays.sort(strs);
        int i = 0, len = Math.min(strs[0].length(), strs[strs.length - 1].length());
        while (i < len && strs[0].charAt(i) == strs[strs.length - 1].charAt(i)) i++;
        return strs[0].substring(0, i);
    }
}

C++구현 LeetCode(14.최 장 공동 접두사)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 최 장 공동 접두사 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 부탁드립니다!