Leetcode: 文字列の最大公約数

問題ステートメント 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))

になります。 スペースの複雑さ:

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

以上がLeetcode: 文字列の最大公約数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。