[Python] Why does Anagram have a time complexity of O(n+m) instead of O(n)

Discussão em 'Python' iniciado por Stack, Fevereiro 20, 2025.

  1. Stack

    Stack Membro Participativo

    I was going through few leetcode problems and came across the Anagram Problem. The time complexity for the solution below was mentioned as O(n+m).

    We are looking at the length of both strings which should be O(1) and we are looping over len(s) which is same as len(t) => Which should be O(n) and the other loop O(26), => O(1) + O(n) + O(26) would just be O(n).

    Why is our time complexity not O(n) and O(n+m)?

    class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
    if len(s) != len(t):
    return False

    count = [0] * 26
    for i in range(len(s)):
    count[ord(s) - ord('a')] += 1
    count[ord(t) - ord('a')] -= 1

    for val in count:
    if val != 0:
    return False
    return True

    Continue reading...

Compartilhe esta Página