Проверить, встречается ли подстрока «10» в данной двоичной строке во всех возможных заменах '?' с 1 или 0
Дана строка S , состоящая только из «0» , «1» и «?» , задача состоит в том, чтобы проверить, существует ли подстрока «10» во всех возможных заменах символа '?' с 1 или 0 .
Примеры:
Input: S = “1?0”
Output: Yes
Explanation:
Following are all the possible replacements of ‘?’:
- Replacing the ‘?’ with 0 modifies the string to “100”. In the modifies string, the substring “10” occurrs.
- Replacing the ‘?’ with 1 modifies the string to “110”. In the modifies string, the substring “10” occurrs.
From the above all possible replacements, the substring “10” occurs in all the replacements, therefore, print Yes.
Input: S= “??”
Output: No
Подход: данная проблема может быть решена с помощью жадного подхода, основанного на наблюдении, что если строка S содержит много последовательных '?' , его можно заменить одним '?' так как в худшем случае мы можем заменить его на все 1 или 0 .
Поэтому идея состоит в том, чтобы создать новую строку из заданной строки S , заменив непрерывный '?' с одним '?' а затем проверить, существует ли подстрока «10» или «1?0» , тогда возможно получить «10» в качестве подстроки после всех возможных замен, поэтому выведите Yes . В противном случае выведите Нет .
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N)
Вспомогательное пространство: O(N)
Примечание. Тот же подход можно использовать и для подстрок «00»/»01»/»11″ с небольшими изменениями.