Πιο επίσημη ονομασία — προσεγγιστική αντιστοιχία συμβολοσειράς (εύρεση προσεγγιστικής αντιστοιχίας). Απαιτείται να ελεγχθεί αν η πρώτη σειρά είναι μια υποσειρά της δεύτερης. Υποσειρά είναι όταν μπορεί να ληφθεί η πρώτη σειρά από τη δεύτερη διαγράφοντας ορισμένους χαρακτήρες. Εισαγωγή: 'car', 'cartwheel' Έξοδος: true Εισαγωγή: 'cwhl', 'cartwheel' Έξοδος: true Εισαγωγή: 'cwhee', 'cartwheel' Έξοδος: true Εισαγωγή: 'cartwheel', 'cartwheel' Έξοδος: true Εισαγωγή: 'cwheeel', 'cartwheel' Έξοδος: false Εισαγωγή: 'lw', 'cartwheel' Έξοδος: false

Задача — проверить, является ли первая строка подпоследовательностью второй. Это значит, что все символы первой строки встречаются во второй в том же порядке, но не обязательно подряд.

Пример решения на Go:

type void struct{}

func isSubsequence(s, t string) bool {
    i, j := 0, 0
    for i < len(s) && j < len(t) {
        if s[i] == t[j] {
            i++
        }
        j++
    }
    return i == len(s)
}

// Пример использования:
// fmt.Println(isSubsequence("car", "cartwheel")) // true
// fmt.Println(isSubsequence("cwheeel", "cartwheel")) // false

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