LeetCode:14. 最長共通接頭辞(C++)

タイトル:
文字列配列の最長の共通接頭辞を検索する関数を作成します.
共通接頭辞が存在しない場合、空の文字列""が返されます.
例1:

  : ["flower","flow","flight"]
  : "fl"

例2:

  : ["dog","racecar","car"]
  : ""
  :          。

説明:
すべての入力には、小文字a-zのみが含まれます.
回答:
1.分治解法を書いた:配列全体の共通接頭辞=対(左半分の共通接頭辞&右半分の共通接頭辞)で共通接頭辞を1回求める.

class Solution {
public:
    string longestCommonPrefix(vector& strs) {
        if (strs.empty()) {
            return "";
        }
        else if(strs.size() == 1) {
            return strs[0];
        }
        else {
            int half = strs.size() / 2;
            vector frontHalf(strs.begin(), strs.begin() + half);
            vector backHalf(strs.begin() + half, strs.end());
            string front = longestCommonPrefix(frontHalf);
            string back = longestCommonPrefix(backHalf);
            string result = "";
            for (int i = 0; i < min(front.length(), back.length()); i++) {
                if (front[i] != back[i]) {
                    break;
                }
                result.append(1, front[i]);
            }
            return result;
        }
    }
};

2.単純で乱暴なスキャンスペースの複雑さはさらに低い:

class Solution {
public:
    string longestCommonPrefix(vector& strs) {
        int index = 0;
        if (strs.empty()) {
            return "";
        }
        for (int i = 0; i < strs[0].length(); i++) {
            char current = strs[0][index];
            //  strs[0][i]，strs[1][i]，strs[2][i]    
            for (string str: strs) {
                /* strs          i       index     
                （strs[0][index] str             i    
                  index    i）*/
                if (str.length() == i || current != str[index]) {
                    return str.substr(0, index);
                }
            }
            index++;
        }
        //  index           1 
        return strs[0].substr(0, index);
    }
};

3.もう1つのスキャン方法:最初の2つの文字列の共通接頭辞を求めることができ、その後、この接頭辞と後ろの文字列で共通接頭辞をもう一度求めることができます.完全な配列を巡るまで続けます.

class Solution {
public:
    string longestCommonPrefix(vector& strs) {
        if (strs.empty()) {
            return "";
        }
        if (strs.size() == 1) {
            return strs[0];
        }

        string prefix = strs[0];
        //  prefix， ； prefix strs[1], strs[2] ... *strs.end()    
        for (int i = 1; i < strs.size(); i++) {
            int lastIndex = min(prefix.length(), strs[i].length());
            for (int j = 0; j < lastIndex; j++) {
                if (prefix[j] != strs[i][j]) {
                    lastIndex = j;
                    break;
                }
            }
            prefix = prefix.substr(0, lastIndex);
            
        }
        return prefix;
        
           
    }
};