【LeetCode】567. Permutation in String 解答・解説【Python】

スポンサーリンク
この記事は約3分で読めます。

学習メモ

自分の言葉で書くことで理解できていない部分をハッキリさせたい。

スポンサーリンク

問題

原文

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1‘s permutations is the substring of s2.

 

Example 1:

Example 2:

 

Constraints:

  • 1 <= s1.length, s2.length <= 104
  • s1 and s2 consist of lowercase English letters.

 

内容

2つの文字列s1,s2が与えられます。s1の順列がs2に含まれている場合はTrue、そうでなければFalseを返してください。つまり、s1の順列がs2の部分文字列ならTrueを返してください。

 

s1の文字列を並び替えた文字列が2に含まれていればTrueを返すという理解です。

 

※正しくない可能性があります。

解答

解答1:Python,スライディングウインドウ

・計算量

time:4014ms

space:13.9mb

 

・スライディングウインドウについて

TCPの用語にも出てくるが、 それとは別。配列内を窓のように範囲を指定して左から右にずらしながら走査していく。

窓の左端の位置、窓の右端の位置をtwo pointerでずらしながら指定したり、窓の幅を使って場合分けしながら処理を記述する。今回はs1の要素数と窓の幅が一致するかで分岐した。

二重ループで総当たりをすると時間計算量がO(n^2)になるが、スライディングウインドウだと計算量を削減できる。

 

解答2:

 

 

補足・参考・感想

■メモ

・2つの文字列が一致するかを確認するには、それぞれ並べ替えてから比較すると良い。

 

■参考

■感想

 

前:19. Remove Nth Node From End of List

次:733. Flood Fill

LeetCode 解答・解説記事一覧

コメント