python - Is My Time Complexity Analysis for Finding Universal Words O(m * k^2 + n*k) correct? - Stack Overflow

admin管理员组

文章数量:1123789

I’m given two string arrays, words1 and words2. A string b is a subset of string a if all characters in b appear in a with at least the same frequency. I need to find all strings in words1 that are universal, meaning every string in words2 is a subset of them. I need to return those universal strings from words1 in any order.

I've written a function to find universal words from two lists, words1 and words2. The function uses a hashmap to store character frequencies from words2 and then checks each word in words1 against these frequencies. The code passed all the test cases but I am confused about analyzing time complexity.

For time complexity:

Processing all words in words2 takes O(m * k), where m = length of words2 and k = average word length. Checking all words in words1 involves O(n * 26), where n = length of words1, and 26 is the max number of hashmap keys (a-z).

If I consider the count() in both the loops it will make whole time complexity O(m * k^2 + n*k). Is this the correct analysis?

def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:
    ans = []
    hmap = {}

    for i in words2:
        for j in i:
            if j in hmap.keys():
                hmap[j] = max(hmap[j], i.count(j))
            else:
                hmap[j] = i.count(j)

    for j in words1:
        flag = True
        for k in hmap.keys():
            if hmap[k] > j.count(k):
                flag = False
                break

        if flag:
            ans.append(j)

    return ans

I’m given two string arrays, words1 and words2. A string b is a subset of string a if all characters in b appear in a with at least the same frequency. I need to find all strings in words1 that are universal, meaning every string in words2 is a subset of them. I need to return those universal strings from words1 in any order.

I've written a function to find universal words from two lists, words1 and words2. The function uses a hashmap to store character frequencies from words2 and then checks each word in words1 against these frequencies. The code passed all the test cases but I am confused about analyzing time complexity.

For time complexity:

Processing all words in words2 takes O(m * k), where m = length of words2 and k = average word length. Checking all words in words1 involves O(n * 26), where n = length of words1, and 26 is the max number of hashmap keys (a-z).

If I consider the count() in both the loops it will make whole time complexity O(m * k^2 + n*k). Is this the correct analysis?

def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:
    ans = []
    hmap = {}

    for i in words2:
        for j in i:
            if j in hmap.keys():
                hmap[j] = max(hmap[j], i.count(j))
            else:
                hmap[j] = i.count(j)

    for j in words1:
        flag = True
        for k in hmap.keys():
            if hmap[k] > j.count(k):
                flag = False
                break

        if flag:
            ans.append(j)

    return ans

• python
• algorithm
• time-complexity

Share Improve this question Follow edited 20 hours ago Nyctophilic Enigma asked yesterday Nyctophilic EnigmaNyctophilic Enigma 2111 silver badge44 bronze badges New contributor Nyctophilic Enigma is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct. 2

• @trincot I apologize for this; thank you for mentioning it; I have edited the post and will be more careful next time. I only wanted to know if I had analyzed the time complexity correctly or not. – Nyctophilic Enigma Commented yesterday
• @trincot Thank you for pointing this out; I have changed the title and will avoid these things in the future. – Nyctophilic Enigma Commented 14 hours ago

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 3

Indeed, the call of count represents O(

本文标签： pythonIs My Time Complexity Analysis for Finding Universal Words O(m * k2n*k) correctStack Overflow