Временная сложность определения, является ли строка подмножеством другой строки

Question

Что такое Big-O для определения, является ли строка подмножеством другой строки? Другими словами, содержит ли строка все символы другой строки?

Например, A = 'string' B = 'gti', B является подмножеством A.

Мой подход использовать все символы A для создания карты. Затем выполните итерацию B для перекрестной проверки с картой. Big-O этого метода O(m + n). Это лучшая временная сложность в худшем случае, которую я могу получить?

Answer 1

Если вы не можете решить проблему без (в худшем случае), по крайней мере, проверки каждого символа каждой строки, вы не сможете сделать лучше, чем O (m + n) (при условии, что m & n - это две длины строки).