проверить, находятся ли буквы строки в последовательном порядке в другой строке - PullRequest
Новая
       4

проверить, находятся ли буквы строки в последовательном порядке в другой строке

0 голосов
/ 14 ноября 2018

Если бы просто проверяли, есть ли буквы в строке test_string также в строке control_string,

У меня не было бы этой проблемы.

Я просто воспользуюсь приведенным ниже кодом. 

if set(test_string.lower()) <= set(control_string.lower()):
    return True

Но я также сталкиваюсь с довольно запутанной задачей выяснить, находятся ли перекрывающиеся буквы в

control_string в том же порядке, что и в test_string.

Например, 

test_string = 'Dih'
control_string = 'Danish'
True

test_string = 'Tbl'
control_string = 'Bottle'
False

Я думал об использовании итератора for для сравнения индексов алфавитов, но довольно сложно придумать подходящий алгоритм. 

for i in test_string.lower():
    for j in control_string.lower():
        if i==j:
            index_factor = control_string.index(j)

Мой план - сравнитьпервичный индексный коэффициент для следующего фактора, и если первичный индексный фактор оказывается больше, чем другой, функция возвращает False.

Я застрял на том, как сравнить эти index_factors в цикле for.

Как мне подойти к этой проблеме?

Ответы [ 6 ]

0 голосов
/ 14 ноября 2018

Вы можете использовать find(letter, last_index), чтобы найти вхождение нужной буквы после обработанных букв. 

def same_order_in(test, control):
    index = 0
    control = control.lower()
    for i in test.lower():
        index = control.find(i, index)
        if index == -1:
            return False
        # index += 1 # uncomment to check multiple occurrences of same letter in test string  
    return True

Если в тестовой строке есть повторяющиеся буквы, такие как: 

test_string = 'Diih'
control_string = 'Danish'

С закомментированной строкой same_order_in(test_string, control_string) == True

и без комментариев same_order_in(test_string, control_string) == False

0 голосов
/ 14 ноября 2018

Вы можете просто join символов в строке test преобразовать в регулярное выражение , допуская любые другие символы .* между ними, а затем re.search этот шаблон в control строка. 

>>> test, control = "Dih", "Danish"
>>> re.search('.*'.join(test), control) is not None
True
>>> test, control = "Tbl", "Bottle"
>>> re.search('.*'.join(test), control) is not None
False

Без использования регулярных выражений вы можете создать iter из строки control и использовать два вложенных цикла, 1) break, входящие из внутреннего цикла, и else, возвращающие False пока все символы в test не будут найдены в control. Важно создать iter, даже если control уже итеративен, чтобы внутренний цикл продолжался там, где он в последний раз остановился. 

def check(test, control):
    it = iter(control)
    for a in test:
        for b in it:
            if a == b:
                break
        else:
            return False
    return True

Вы можете даже сделать это в одну (ну, две) строки, используя all и any: 

def check(test, control):
    it = iter(control)
    return all(any(a == b for b in it) for a in test)

Сложность для обоих подходов должна быть O (n), где n - максимальное количество символов.

1) Концептуально это похоже на то, что делает @ jpp , но ИМХО немного понятнее.

0 голосов
/ 14 ноября 2018

Элегантное решение с использованием генератора: 

def foo(test_string, control_string):
    if all(c in control_string for c in test_string):
        gen = (char for char in control_string if char in test_string)
        if all(x == test_string[i] for i, x in enumerate(gen)):
            return True
    return False

print(foo('Dzn','Dahis')) # False
print(foo('Dsi','Dahis')) # False
print(foo('Dis','Dahis')) # True

Сначала проверьте, все ли буквы в test_string содержатся в control_string. Затем проверьте, похож ли заказ на заказ test_string.

0 голосов
/ 14 ноября 2018

Вот одно из решений.Идея состоит в том, чтобы перебрать строку control string first и получить значение, если оно соответствует следующему символу test.Если общее количество совпадений равно длине test, то ваше условие выполнено. 

def yield_in_order(x, y):
    iterstr = iter(x)
    current = next(iterstr)
    for i in y:
        if i == current:
            yield i
            current = next(iterstr)

def checker(test, control):
    x = test.lower()
    return sum(1 for _ in zip(x, yield_in_order(x, control.lower()))) == len(x)

test1, control1 = 'Tbl', 'Bottle'
test2, control2 = 'Dih', 'Danish'

print(checker(test1, control1))  # False
print(checker(test2, control2))  # True

@ tobias_k's answer имеет более чистую версию этого.Если вам нужна дополнительная информация, например, как выравнивается много букв до того, как найден разрыв, вы можете тривиально настроить функцию checker, чтобы она возвращала sum(1 for _ in zip(x, yield_in_order(...))).

0 голосов
/ 14 ноября 2018

Простой способ - использовать аргумент key в sorted, который служит ключом для сравнения сортировки: 

def seq_order(l1, l2):
    intersection = ''.join(sorted(set(l1) & set(l2), key = l2.index))
    return True if intersection == l1 else False

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

Функция возвращает True или False соответственно. Используя ваши примеры: 

seq_order('Dih', 'Danish')
#True

seq_order('Tbl', 'Bottle')
#False

seq_order('alp','apple')
#False
0 голосов
/ 14 ноября 2018

Рекурсия - лучший способ решения таких проблем.Вот тот, который проверяет на последовательное упорядочение. 

def sequentialOrder(test_string, control_string, len1, len2): 

    if len1 == 0:     # base case 1
        return True

    if len2 == 0:     # base case 2
        return False

    if test_string[len1 - 1] == control_string[len2 - 1]: 
        return sequentialOrder(test_string, control_string, len1 - 1, len2 - 1)  # Recursion 

    return sequentialOrder(test_string, control_string, len1, len2-1)

test_string = 'Dih'
control_string = 'Danish'

print(isSubSequence(test_string, control_string, len(test_string), len(control_string)))

Выходы: 

True

и False для 

test_string = 'Tbl'
control_string = 'Bottle'

Вот итерационный подход, который делает то же самоевещь, 

def sequentialOrder(test_string,control_string,len1,len2): 

    i = 0
    j = 0

    while j < len1 and i < len2: 
        if test_string[j] == control_string[i]:     
            j = j + 1    
        i = i + 1

    return j==len1 

test_string = 'Dih'
control_string = 'Danish'

print(sequentialOrder(test_string,control_string,len(test_string) ,len(control_string)))
...