問題ステートメント 1071. 文字列の最大公約数

2 つの文字列 s と t について、s = t t t ... t t (つまり、t がそれ自身と 1 回以上連結されている) の場合に限り、「t は s を割る」と言います。

2 つの文字列 str1 と str2 を指定すると、x が str1 と str2 の両方を分割するような最大の文字列 x を返します。

私の思考プロセス

リートコードでは簡単な問題としてマークされていましたが、すぐに解決策を思いつくのは難しいと認めざるを得ません。

leetcode が提供するテスト ケースを確認して、私の混乱を説明しましょう。

テストケース

入力: str1 = "ABCABC"、str2 = "ABC"
出力: "ABC"

入力: str1 = "ABABAB"、str2 = "ABAB"
出力: "AB"

問題ステートメントとテスト ケース 1 から、両方の文字列を取得できる最大の文字列 ("ABC") を連結して出力​​する必要があることがわかりました。 (デフォルトの文字列 "ABC" === str2 および "ABC" "ABC" === str1)。

しかし、テスト ケース 2 を見ると、両方の文字列を作成できる最長の文字列である「ABAB」を出力する必要があるという私の理解が正しくなかったことがすぐにわかりました。しかし、私はすぐにコードを作成し、解決策を計画し始めました。 (初歩的なミス?)

失敗したこと/成功したこと

私が解決策を計画できたのは次の場合のみでした:

1. 2 つの文字列の GCD を見つけます。
2. 最小の文字列の長さから GCD まで反復します
3. 最小の文字列から現在の反復値までの部分文字列を取得します。
4. 両方の文字列にその部分文字列が含まれている場合は、その部分文字列を答えとして返します。
5. 文字列が見つからない場合は "" を返します。

ご覧のとおり、私の解決策は、str1 に str2 が含まれているが、その他の追加文字も含まれている文字列では失敗しました。 s = t t ... t t.

私はneetcodeのソリューションに助けを求めなければなりませんでした。私は自分の問題をすぐに理解しました:

1. 文字列自体ではなく、文字列の長さの GCD を見つけていました。これらの文字列を繰り返す文字列を見つける必要があります。文字を残さずに両方の文字列を作成できます。

2. なぜ「ABAB」がテスト ケース 2 の答えになり得ないことがわかりました:

• 両方の文字列を均等に分割する x を見つける必要があります。したがって、文字列として「ABAB」を使用すると、str2 を完全に作成できますが、str1 については「ABABABAB」になります。 "AB" が 2 つ余ってしまい、x.

を組み合わせて str1 を完全に作成したとは言えません。

• "ABAB" 長さ 4 および "ABABAB" 長さ 6。2 つの文字列の GCD = 2。したがって、出力は長さ 2 の文字列である必要があります。

出力

時間と空間の複雑さ

時間計算量: 最悪の場合、Min(str1,str2) を反復処理し、str1 と str2 を再作成する必要があるため、それが (str1.length str2.length) になるため、全体の時間計算量はO(min(str1,str2) * (str1.length str2.length))

Space Complexity: O(1) 追加のスペースは必要ありません。