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

学習メモ

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

問題
1. 原文
2. 内容
解答
1. 解答1：Python,スライディングウインドウ
2. 解答2：
補足・参考・感想

問題

原文

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:

Input: s1 = "ab", s2 = "eidbaooo" Output: true Explanation: s2 contains one permutation of s1 ("ba").

1
2
3

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input: s1 = "ab", s2 = "eidboaoo" Output: false

1
2

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

Constraints:

1 <= s1.length, s2.length <= 10⁴

s1 and s2 consist of lowercase English letters.

内容

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

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

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

解答

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

"""
・一時変数にs2の文字列を1つずつ追加し、s1と同じ長さになった時に一致するか確認する。
　→順序の違う文字列が一致するか確認するときは並び替えが使える
・一致した場合はTrue、一致しない場合は一時変数の2文字目以降を抜き出して上記の操作を繰り返す
"""

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        target_string = ''.join(sorted(s1))
        current_string = ''
        
        for char in s2:
            #current_stringに1文字追加
            current_string += char
            #長さが一致したとき
            if len(current_string) == len(target_string):
                #ソートしたcurrent_stringを1つに結合し、target_stringと一致したらTrueを返す
                if ''.join(sorted(current_string)) == target_string:
                    return True
                #一致しない場合は1文字目以降を抽出する
                current_string = current_string[1:]
        return False

"""

・一時変数にs2の文字列を1つずつ追加し、s1と同じ長さになった時に一致するか確認する。

　→順序の違う文字列が一致するか確認するときは並び替えが使える

・一致した場合はTrue、一致しない場合は一時変数の2文字目以降を抜き出して上記の操作を繰り返す

"""

class Solution:

def checkInclusion(self, s1: str, s2: str) -> bool:

target_string = ''.join(sorted(s1))

current_string = ''

for char in s2:

#current_stringに1文字追加

current_string += char

#長さが一致したとき

if len(current_string) == len(target_string):

#ソートしたcurrent_stringを1つに結合し、target_stringと一致したらTrueを返す

if ''.join(sorted(current_string)) == target_string:

return True

#一致しない場合は1文字目以降を抽出する

current_string = current_string[1:]

return False

・計算量

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 解答・解説記事一覧