Formelere naam — benaderingsstringovereenkomst (het vinden van een benaderingsovereenkomst). Het is nodig om te controleren of de eerste string een subsequente is van de tweede. Een subsequente is wanneer je de eerste string uit de tweede kunt krijgen door sommige tekens te verwijderen. Input: 'car', 'cartwheel' Output: true Input: 'cwhl', 'cartwheel' Output: true Input: 'cwhee', 'cartwheel' Output: true Input: 'cartwheel', 'cartwheel' Output: true Input: 'cwheeel', 'cartwheel' Output: false Input: 'lw', 'cartwheel' Output: 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

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