はじめに

---

先頭から何文字まで共通かどうか求める問題．

<例>
["flower","flow","flight"] -> "fl"
["dog","racecar","car"] -> ""

コード全体

---

string longestCommonPrefix(vector<string>& strs) {
  if(strs.empty()) return "";
  if(strs.size()==1) return strs[0];
  size_t minLength = strs[0].length();
  for(size_t i=1; i<strs.size(); ++i) minLength = min(minLength, strs[i].length());
  for(size_t i=0; i<minLength; ++i){
    for(size_t strIdx=1; strIdx<strs.size(); ++strIdx){
      if(strs[0][i] != strs[strIdx][i]) return strs[0].substr(0,i);
    }
  }
  return strs[0].substr(0,minLength);
}

解説

---

文字列が一つもない場合は""（からの文字列）を返す。

string longestCommonPrefix(vector<string>& strs) {
  if(strs.empty()) return "";

minLengthは、一番短い文字列の長さを表す。そのため、for-loopで更新して最短長を求める。

  size_t minLength = strs[0].length();
  for(size_t i=1; i<strs.size(); ++i) minLength = min(minLength, strs[i].length());

インデックス番号が0からminLengthまで全ての文字列の文字が一致するか確認する。 一致しなかった段階で、その長さの部分文字列をstd::substr()によって返す。

  for(size_t i=0; i<minLength; ++i){
    for(size_t strIdx=1; strIdx<strs.size(); ++strIdx){
      if(strs[0][i] != strs[strIdx][i]) return strs[0].substr(0,i);
    }
  }

この時点でプログラムが継続されているということは、minLengthまで全て一致したという事なので、0~minLengthの部分文字列を返す。

  return strs[0].substr(0,minLength);
}