C++でLeetCodeの「Longest Palindromic Substring」問題を解く
Problem
https://leetcode.com/problems/longest-palindromic-substring/
Answer
O(N3)
class Solution {
private:
bool check(string &subString, int subStringSize){
int i = 0;
while(i < j) {
if(subString[i] != subString[j]) {
return false;
}
i++;
j--;
}
return true;
}
public:
string longestPalindrome(string s) {
int inputStringSize = s.size();
vector<string> substrings;
for (int i = 0; i < inputStringSize; i++) {
string tmp = "";
for (int j = i; j < inputStringSize; j++) {
tmp += s[j];
substrings.push_back(tmp);
}
}
int maxLength = 0;
string longestSubstring = substrings[0];
int subStringsSize = substrings.size();
for (int i = 0; i < subStringsSize; i++) {
int subStringSize = substrings[i].size();
if(check(substrings[i], subStringSize - 1)){
if(subStringSize > maxLength){
maxLength = subStringSize;
longestSubstring = substrings[i];
}
}
}
return longestSubstring;
}
};
この問題の解決策を考えてみよう。
この問題は、すべての部分文字列をチェックすることで解決できる。 ある部分文字列が回文かどうかは、その部分文字列の先頭と末尾から中央に向かって同じ文字があるかどうかで判断する。
例えば、文字列 babd をすべての可能な部分文字列に分割してみよう：
b, ba, bab, babd
b, ba, bab, babd, d.
次に、部分文字列の先頭と末尾の文字が同じかどうかを、部分文字列の途中までチェックする。
例えば
bは最初の文字（b）と最後の文字（b）が同じなので回文の部分文字列である。
baは最初の文字(b)と最後の文字(a)が同じではないので、回文の部分文字列ではない。
bab は最初の文字 (b) と最後の文字 (b) が同じなので、回文部分文字列である。
babdは最初の文字（b）と最後の文字（d）が同じではないので、回文部分文字列ではない。
この処理をすべての部分文字列に対して続ける。
しかし、この解決策は、すべての部分文字列を作成するのにO(n2)、部分文字列が回文かどうかをチェックするのにO(n)の時間複雑度を持つため、性能は最適ではない。
時間複雑度 O(n2)だけの解決策がある。この解を探ってみよう。
O(N2)
class Solution {
private:
bool solve(vector<vector<bool>> &dp, int startIndex, int endIndex, string &inputString){
if(startIndex == endIndex){
return dp[startIndex][endIndex] = true;
}
if(endIndex - startIndex == 1){
if(s[startIndex] == s[endIndex]){
return dp[startIndex][endIndex] = true;
}
else{
return dp[startIndex][endIndex] = false;
}
}
if(s[startIndex] == s[endIndex] && dp[startIndex + 1][endIndex - 1] == true){
return dp[startIndex][endIndex] = true;
} else {
return dp[startIndex][endIndex] = false;
}
}
public:
string longestPalindrome(string s) {
int inputStringSize = s.size();
int startIndexOfMaxLength = 0; int maxLength = 0;
vector<vector<bool>> dp(inputStringSize, vector<bool>(inputStringSize, false));
for(int g = 0; g < inputStringSize; g++){
for(int startIndex = 0, endIndex = g; endIndex < inputStringSize; startIndex++, endIndex++){
solve(dp, startIndex, endIndex, s);
if(dp[startIndex][endIndex] == true){
if(endIndex - startIndex + 1 > maxLength){
startIndexOfMaxLength = startIndex;
maxLength = endIndex - startIndex + 1;
}
}
}
}
return inputStringSize.substr(startIndexOfMaxLength, maxLength);
}
};
本解法は動的計画法を用いている。 小問題に分割された問題を解き、小問題の答えをメモとして保存します。
解の内部を見てみよう。
string longestPalindrome(string s) {
int inputStringSize = s.size();
int startIndex = 0; int maxLength = 0;
vector<vector<bool>> dp(inputStringSize, vector<bool>(inputStringSize, false));
inputStringSize 変数は引数 s の長さ。 startIndex変数は対象となる文字列の先頭インデックスである。 maxLength変数は最長の回文文字列です。 dp変数は、小さなプログラムをメモとして保存し、2次元配列として答えを保存したものです。
次に、2重ループで使用されるsolve関数を見てみよう。
bool solve(vector<vector<bool>> &dp, int startIndex, int endIndex, string &inputString){
if(startIndex == endIndex){
return dp[startIndex][endIndex] = true;
}
if(endIndex - startIndex == 1){
if(s[startIndex] == s[endIndex]){
return dp[startIndex][endIndex] = true;
}
else{
return dp[startIndex][endIndex] = false;
}
}
if(s[startIndex] == s[endIndex] && dp[startIndex + 1][endIndex - 1] == true){
return dp[startIndex][endIndex] = true;
} else {
return dp[startIndex][endIndex] = false;
}
}
startIndexがendIndexと等しい場合、dp[startIndex][endIndex]にtrueを代入する。
例えば
startIndex が 0 で endIndex が 0 の場合、 inputString は1語である。これは回文文字列に等しい。
if(endIndex - startIndex == 1){
if(s[startIndex] == s[endIndex]){
return dp[startIndex][endIndex] = true;
}
else{
return dp[startIndex][endIndex] = false;
}
}
dp[startIndex][endIndex] に true を代入するのは、endIndex - startIndex が 1 に等しく、かつ s[StartIndex] が s[endIndex] に等しい場合である。
例えば
s が aa で、startIndex が 0 で、endIndex が 1 の場合、endIndex(1) - startIndex(0) は 1 に等しく、s[0] は a で、s[1] は a で、互いに等しい。
これは回文文字列である。
dp[startIndex][endIndex] に false を代入するのは、endIndex - startIndex が 1 で、かつ s[StartIndex] が s[endIndex] と等しくない場合です。
例えば
s が ab で、startIndex が 0 で、endIndex が 1 で、endIndex(1) - startIndex(0) が 1 で、s[0] が a で、s[1] が b で、互いに等しくない場合。
これは回文文字列ではない。
if(s[startIndex] == s[endIndex] && dp[startIndex + 1][endIndex - 1] == true){
return dp[startIndex][endIndex] = true;
} else {
return dp[startIndex][endIndex] = false;
}
s[startIndex]とs[endIndex]が等しく、かつdp[startIndex + 1][endIndex - 1]がtrueの場合、dp[startIndex][endIndex]にtrueを代入する。
例えば
sがabaでstartIndexが0でendIndexが2の場合、s[startIndex]とs[endIndex]は等しい。
sがabaでdp[0 + 1][2 - 1]が真なら回文文字列。
dp[1][1]は小さい部分文字列から計算されるので、すでに計算されています。dp[1][1]がbなので、dp[1][1]はtrueです。
s[startIndex]とs[endIndex]が等しくないか、dp[startIndex + 1][endIndex - 1]が真でない場合、dp[startIndex][endIndex]に偽を代入します。
例えば
sがabcd、startIndexが0、endIndexが3、dp[0 + 1][3 - 1]が偽の場合、回文文字列ではありません。
dp[1][2]は小さい部分文字列から計算されるので、すでに計算されています。dp[1][2]はbcなので偽です。
for(int g = 0; g < inputStringSize; g++){
for(int i = 0, j = g; j < inputStringSize; i++, j++){
solve(dp, i, j, s);
ループは、1つの単語からすべての単語までのすべての部分文字列に対してsolve関数を実行する。
例えば
inputStringSizeはabaである。
まず、solve(dp, 0, 0, aba)。部分文字列が a なので、dp[0][0] が真になる。
次に、solve(dp, 1, 1, aba). dp[1][1] は部分文字列が b なので真である。
dp[2][2] は部分文字列が a なので真である。
dp[0][1] は部分文字列が ab なので偽である。
dp[1][2] は部分文字列が ba なので偽である。
dp[0][2] は部分文字列が aba なので真である。
if(dp[startIndex][endIndex] == true){
if(endIndex - startIndex + 1 > maxLength){
startIndexOfMaxLength = startIndex;
maxLength = endIndex - startIndex + 1;
}
}
solve関数で計算されたdp[startIndex][endIndex]が真で、かつmaxLengthである endIndex - startIndex + 1 が現在のmaxLengthより大きければ、startIndexをstartIndexOfMaxLengthに、endIndex - startIndex + 1 をmaxLengthに再割り当てする。
最後に，longestPalindrome関数は，最長の回文部分文字列であるinputStringSize.substr(startIndexOfMaxLength, maxLength)を返します．
英語で書いたものを機械翻訳で日本語に翻訳しています。
