Как проверить, является ли одна строка подпоследовательностью другой?

Как проверить, является ли одна строка подпоследовательностью другого?

Это более слабое условие, чем подстрока. Например, "iran" не является подстрокой "ireland", но является подпоследовательностью IRelANd. Разница заключается в том, что подпоследовательность не должна быть смежной.

Другие примеры:

'indonesia' содержит 'india'. INDonesIA
'romania' содержит 'oman'. rOMANia
'malawi' содержит 'mali'. MALawI

Мотивация: моим друзьям нравится игра слов. Вчера мы играли "страны внутри стран". Мне любопытно, есть ли какие-то пары, которые мы пропустили.

Изменить: если вы не знакомы с математическим определением подпоследовательности

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

Ответ 1

Я сделал

def is_subsequence(x, y):
    """Test whether x is a subsequence of y"""
    x = list(x)
    for letter in y:
        if x and x[0] == letter:
            x.pop(0)

    return not x

Ответ 2

def is_subseq(x, y):
    it = iter(y)
    return all(any(c == ch for c in it) for ch in x)

assert is_subseq('india', 'indonesia')
assert is_subseq('oman', 'romania')
assert is_subseq('mali', 'malawi')
assert not is_subseq('mali', 'banana')
assert not is_subseq('ais', 'indonesia')
assert not is_subseq('ca', 'abc')

Также работает для любых итераций:

assert is_subseq(['i', 'n', 'd', 'i', 'a'],
                 ['i', 'n', 'd', 'o', 'n', 'e', 's', 'i', 'a'])

UPDATE

Стефан Похманн предложил это.

def is_subseq(x, y):
    it = iter(y)
    return all(c in it for c in x)

Обе версии используют итераторы; Итератор дает элементы, которые не были получены в предыдущей итерации.

Например:

>>> it = iter([1,2,3,4])
>>> for x in it:
...     print(x)
...     break
...
1
>>> for x in it:  # `1` is yielded in previous iteration. It not yielded here.
...     print(x)
...
2
3
4

Ответ 3

Просто продолжайте искать следующий символ вашей потенциальной подпоследовательности, начиная с последнего найденного. Как только один из символов не может быть найден в остальной части строки, это не подпоследовательность. Если все символы могут быть найдены таким образом, это:

def is_subsequence(needle, haystack):
    current_pos = 0
    for c in needle:
        current_pos = haystack.find(c, current_pos) + 1
        if current_pos == 0 : return False
    return True

Ответ 4

def subsequence(seq, subseq):
    seq = seq.lower()
    subseq = subseq.lower()
    for char in subseq:
        try:      
            seq = seq[seq.index(char)+1:]            
        except:
            return False
    return True

Ответ 5

Я столкнулся с подобным вопросом о GOOGLE Interview здесь

@Colonel Panic

Вам даже не нужно преобразовывать две строки в списки для push pop-операций

Просто мы можем использовать два метода указателя для этого в O (n) O (1)

Предположим, что

Ирландия и Иран

начинаем с двух указателей я и j, указывающих на два первых начала строк

bool Is_subsequence_of(string &A,string &B)
{
  // Is B a subsequence of A //
  int i = 0,j = 0;
  while((i < A.length())&&(j < B.length()))
  {
    if(A[i] == B[j]){i++;j++;}
    else i++;
  } 
  if(j == B.length())return true;
  else return false;
}

Другим подходом может быть cound здесь

таким образом givn здесь вы также можете найти количество экземпляров, которые строка ccurs как подпоследовательность другой строки