与えられた文字列内のユニークな部分文字列の検索

文字列abcを考えると、以下のユニークな文字列を生成することです.

['abc', 'bc', 'ab', 'c', 'b', 'a']

キューで
我々は、キューの助けを借りてそれを行うことができます.
これがロジックです.

指定された文字列を受け取り、キュー562479142に追加します.

qが空でない間、

、ステップ3 - 5を繰り返してください.

はqの最初の項目をポップします.

これをqという最終結果リストに追加します.

は、resに既にない場合に限り、左の部分文字列(例えばab)と右部分文字列(例えばbc)をキューに追加します.

キューが空であるならば、印刷res.

def findSubstrings(s):

    res = set()
    q = [s]

    while q:

        s = q.pop(0)
        res.add(s)

        x = 0
        y = len(s)-1

        right_string = s[x+1:y+1]
        left_string = s[x:y]

        if right_string and right_string not in res:
            q.append(right_string)

        if left_string and left_string not in res:
            q.append(left_string)

    return res

r = list(findSubstrings('abc'))
r.sort(key=len, reverse=True)
print(r)

# Result:
# ['abc', 'ab', 'bc', 'b', 'c', 'a']

再帰的に
ここではロジックは同じですが、1つのヘルパー関数を使って再帰的に行います.

def findSubstrings(s):

    res = set()

    def helper(s):

        if len(s) <= 0:
            return

        res.add(s)

        right_string = s[1:len(s)]
        left_string = s[0:len(s)-1]

        if right_string not in res:
            helper(right_string)

        if left_string not in res:
            helper(left_string)

    helper(s)

    return res

r = list(findSubstrings('abc'))
r.sort(key=len, reverse=True)
print(r)

# Result:
# ['abc', 'ab', 'bc', 'b', 'c', 'a']

複雑さ
私たちがユニークな値(ここで、Nが与えられたストリングの長さ)をチェックするためにセットを使用しないならば、私はここで最悪のケース時間がresでありえたと思います.


最後の思考
どこでこれを使えますか.したら、基本的なロジックを理解すると、多くの文字列関連の問題を解決するために使用することができます.例:Finding the longest palindromic substring.
これを達成する様々な(より簡単な)方法があるかもしれません、しかし、私はこのアプローチがプロセスを視覚化するのを援助すると思います.読書ありがとうございます!)