2942.Find Words Containing Character

Ссылка на задачу: https://leetcode.com/problems/find-words-containing-character/description/

Описание

Дан 0-indexed массив строк words и символ x.

Необходимо вернуть массив индексов, содержащий индексы тех элементов words, что содержат символ x.

Имейте в виду: порядок элементов искомого массива не имеет значения.

Примечания

0-indexed означает то, что индексация элементов в массиве начинается с нуля.

Примеры

Пример 1

Input:

words

x = ‘e’

Output:

Объяснение: символ ‘e’ содержится в обоих элементах “leet” и “code”. Их индексы 0 и 1 соответственно.

Пример 2

Input:

words

x = ‘a’

Output:

Объяснение: символ ‘a’ содержится только в элементах “abс” и “aaaa”. Их индексы 0 и 2 соответственно.

Ограничения

• 1 <= words.length <= 50

• 1 <= words[i].length <= 50

• ‘x’ - прописная это буква английского алфавита

• words[i] состоит только из прописных букв английского алфавита

Решение

Здесь всего один способ решения задачи. Достаточно пробежаться по всему массиву и ответить на вопрос, содержится ли символ x в элементе текущей итерации.

Алгоритм:

1. Пробегаемся по всему массиву целиком

2. Для текущего i-того элемента определяем, содержится ли в нем x (ответ на этот вопрос получаем с помощью прямого перебора)

3. Если элемент x присутствует в элементе, то к искомому массиву добавляем индекс i

Код:

python

class Solution:
    def findWordsContaining(self, words: List[str], x: str) -> List[int]:
        res = []
        for i in range(len(words)):
            if x in words[i]:
                res.append(i)
        return res

C++

class Solution {
public:
    vector<int> findWordsContaining(vector<string>& words, char x) {
        vector<int> res;
        for (int i = 0; i < words.size(); ++i) {
            if (words[i].find(x) != string::npos) {
                res.push_back(i);
            }
        }
        return res;
    }
};

Сложность алгоритма по времени - O(N*M)

Сложность по времени определяется двумя циклами: внешним и внутренним на каждой итерации внешнего. Внешний представляет собой O(N), где N - размер массива words. Внутренни представляет собой проход по каждому words[i], здесь M - размер самого длинного words[i], так как в самом худшем случае придется полностью перебрать все символы самого длинного words[i]. Так, имеем O(N*M).

Сложность алгоритма по памяти - O(1)

Решение не предполагает никаких дополнительных затрат памяти.