Найти все подстроки в строке в Python 3 с помощью грубой силы

Question

Я хочу найти все подстроки 'A' to 'B' в L = ['C', 'A', 'B', 'A', 'A', 'X', 'B', 'Y', 'A'] с помощью bruteforce, вот что я сделал:

def find_substring(L):
    t = 0
    s = []
    for i in range(len(L) - 1):
        l = []
        if ord(L[i]) == 65:
            for j in range(i, len(L)):
                l.append(L[j])
                if ord(L[j]) == 66:
                    t = t + 1
                    s.append(l)
    return s, t

Теперь мне нужен вывод:

[['A','B'], ['A','B','A','A','X','B'], ['A','A','X','B'], ['A','X','B']]

Но я получаю:

[['A','B','A','A','X','B','Y','A'],['A','B','A','A','X','B','Y','A'],['A','A','X','B','Y','A'],['A','X','B','Y','A']]

Может кто-нибудь сказать мне, что я делаю не так?

Answer 1

Еще один немного другой подход был бы следующим:

L = ['C', 'A', 'B', 'A', 'A', 'X', 'B', 'Y', 'A']

def find_substring(L):
    output = []
    # Start searching for A.
    for i in range(len(L)):
        # If you found one start searching all B's until you reach the end.
        if L[i]=='A':
            for j in range(i,len(L),1):
                # If you found a B, append the sublist from i index to j+1 index (positions of A and B respectively).
                if L[j]=='B':
                    output.append(L[i:j+1])
    return output

result = find_substring(L)
print(result)

Вывод:

[['A', 'B'], ['A', 'B', 'A', 'A', 'X', 'B'], ['A', 'A', 'X', 'B'], ['A', 'X', 'B']]

В случае, если вам нужно понимание списка выше:

def find_substring(L):
    output = [L[i:j+1] for i in range(len(L)) for j in range(i,len(L),1) if L[i]=='A' and L[j]=='B']
    return output

Answer 2

Итак, вы хотите, чтобы все подстроки начинались с 'A' и заканчивались на 'B'?

Когда вы используете код @ Joeidden, который вы можете изменить, нужно for i in range(len(L) - 1): на for i in range(len(L)):, потому что только строкитот конец с 'B' будет добавлен к s.

def find_substring(L):
    s = []
    for i in range(len(L)):
        l = []
        if L[i] == 'A':
            for j in range(i, len(L)):
                l.append(L[j])
                if L[j] == 'B':
                    s.append(l[:])
return s

Answer 3

Лучше сначала найти все индексы 'A' и 'B', затем итерировать по ним, избегая грубой силы.

def find_substrings(lst)
    idx_A = [i for i, c in enumerate(lst) if c == 'A']
    idx_B = [i for i, c in enumerate(lst) if c == 'B']

    return [lst[i:j+1] for i in idx_A for j in idx_B if j > i]

Answer 4

Когда вы добавляете l к s, вы добавляете ссылку в список, который затем продолжаете расти.Вы хотите добавить копию содержимого списка l в момент добавления, чтобы он оставался статичным.

           s.append(l[:])

Это часто задаваемые вопросы;этот вопрос, вероятно, следует закрыть как дубликат.

Answer 5

Проблема в том, что список s содержит ссылки на списки l.

Так что даже если вы добавляете правильные списки l к s, они изменяются последобавленные в качестве будущих итераций цикла j, измените списки l.

Это можно исправить, добавив копию списка l: l[:].

Также, вы можете сравнивать строки напрямую, не нужно конвертировать в ASCII.

def find_substring(L):
    s = []
    for i in range(len(L) - 1):
        l = []
        if L[i] == 'A':
            for j in range(i, len(L)):
                l.append(L[j])
                if L[j] == 'B':
                    s.append(l[:])
    return s

, который теперь работает:

>>> find_substring(['C', 'A', 'B', 'A', 'A', 'X', 'B', 'Y', 'A'])
[['A', 'B'], ['A', 'B', 'A', 'A', 'X', 'B'], ['A', 'A', 'X', 'B'], ['A', 'X', 'B']]

Answer 6

Вы можете сбросить l на копию строки после добавления l l = l[:] сразу после последнего добавления.