指定された文字列の順列が別の指定された文字列よりも辞書編集的に大きいかどうかをチェックします-C++-php.cn

指定された文字列の順列が別の指定された文字列よりも辞書編集的に大きいかどうかをチェックします

王林

リリース： 2023-09-22 08:41:13

転載

1195 人が閲覧しました

指定された文字列の順列が別の指定された文字列よりも辞書編集的に大きいかどうかをチェックします

2 つの文字列が与えられており、指定された文字列の順列が存在するかどうかを確認して、i 番目のインデックス文字で一方の順列が他方の順列よりも大きな値を持つことができるかどうかを確認する必要があります。の。

文字列をソートし、文字列内の各文字を 1 つずつ比較することで、この問題を解決できます。あるいは、2 つの文字列の文字頻度を使用して問題を解決することもできます。

問題文 - 長さ N の文字列 str1 と str2 が与えられています。辞書編集的に一方が他方よりも大きくなるような文字列の順列があるかどうかを確認する必要があります。これは、すべての順列の i 番目のインデックスに、別の文字列順列の i 番目のインデックスの文字よりも大きい文字が含まれている必要があることを意味します。

＃＃＃例＃＃＃

入力

- str1 = "aef"; str2 = "fgh";

出力

–はい

説明

– 「fgh」はすでに「aef」よりも大きくなっています。ここで、ａ＞ｆ、ｇ＞ｅ、ｈ＞ｆである。

入力

– str1 = "adsm"; str2 = "obpc";

出力

–いいえ

説明

– 一方の文字列のすべての文字がもう一方の文字列よりも大きい配置は見つかりません。方法1

このメソッドでは、2 つの文字列を辞書順に並べ替えます。次に、文字列の各文字を比較します。 str1 のすべての文字が str2 より小さい場合、または str2 のすべての文字が str1 より小さい場合、true を返します。それ以外の場合は false を返します。

＃＃＃アルゴリズム＃＃＃

sort() メソッドを使用して文字列を並べ替えます。

isStr1Greater ブール変数を定義し、true で初期化します。
##文字列をトラバースし、str1 の i 番目のインデックス位置にある文字が str2 より小さい場合、isStr1Greater の値を false に更新し、break キーワードを使用してループを中断します
isStr1Greater が true の場合、ループは正常に完了し、true を返します。
次に、文字列を反復処理して、str2 が str1 より大きいかどうかを確認します。 str1 の文字が str2 より大きい場合は、false を返します。
ループが正常に完了した場合は true を返します。
時間計算量 - O(N*logN)、文字列をソートするため。

空間複雑度 - 文字列をソートするには O(N) が必要です。

方法 2

このメソッドでは、両方の文字列の各文字の合計頻度を保存します。その後、累積頻度を使用して、一方が他方よりも大きくなるような文字列の順列を見つけることができるかどうかを判断します。

＃＃＃アルゴリズム＃＃＃

長さ 26 の配列map1とmap2を定義し、それらをゼロに初期化します。

str1の文字の頻度をmap1に格納し、str2の文字の頻度をmap2に格納します。

isStr1 および isStr2 ブール変数を定義し、それらを false に初期化して、str1 が str2 より大きいかどうかを追跡します。

cnt1 変数と cnt2 変数を定義して、文字列文字の累積頻度を保存します。
マップ 1 とマップ 2 を移動します。 cnt1にmap1[i]を追加し、cnt2にmap2[i]を追加します。
cnt1 が cnt2 より大きい場合、str1 から i 番目のインデックスまでの文字の累積頻度は大きくなります。そうである場合、かつ str2 がすでに大きい場合は、false を返します。それ以外の場合は、isStr1 を true
に変更します。
cnt2 が cnt1 より大きい場合、str2 の i 番目のインデックスにある文字の累積頻度は大きくなります。そうであって、str1 がすでに大きい場合は、false を返します。それ以外の場合は、isStr2 を true
に変更します。
最終的に true を返します。
＃＃＃例＃＃＃リーリー＃＃＃出力＃＃＃リーリー
文字の頻度をカウントするため、時間計算量 - O(N)。
空間計算量 - O(26)、文字の頻度を配列に保存するため。

一方の文字列のすべての文字が他方の文字列より大きくなるような 2 つの文字列の順列があるかどうかを確認する方法を学びました。 1 つ目の方法は並べ替え方法を使用し、2 つ目の方法は文字の累積頻度を使用します。