Leetcode:Longest Common Prefix最長共通接頭辞

2564 ワード

私を突き刺して問題を解く
Write a function to find the longest common prefix string amongst an array of strings.

 
class Solution {
public:
    string longestCommonPrefix(vector<string> &strs) {
        if (strs.size() == 0) return "";
        string res;
        for (int i = 0; ; ++i) {
            int j = 0;
            for (j = 0; j < strs.size(); ++j) {
                if (i >= strs.at(j).size() || strs.at(0).at(i) != strs.at(j).at(i)) break;
            }
            if (j < strs.size()) break;
            res += strs.at(0).at(i);
        }
        return res;
    }
};

下付きiは最初の文字列を示し、下付きjはvectorを示す
a   b  c
a   b  d  e  f
a   b  d  e
a   b  c  d
縦比較を用いて,まず縦4個のaを比較し,次に縦4個のbを比較し,次いで第3列のdまで異なることが分かった.
比較の過程で、私たちは注意する必要があります.
1.下付きiの値は1行あたりの文字列の長さより小さくなければならない
2.最初の行と同じ列ではない値が見つかったらbreak
次のことがわかります.
列全体が同じである場合、j値はstrsに等しいに違いない.size()この共通文字が追加され、
j値がstrsより小さい場合size()は、breakが早まったため、異なる値があることを意味し、このとき外層サイクルを中断する