Skip to content

Latest commit

 

History

History
137 lines (112 loc) · 4.51 KB

_3213. Construct String with Minimum Cost.md

File metadata and controls

137 lines (112 loc) · 4.51 KB

3213. Construct String with Minimum Cost

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Completed during Weekly Contest 405 (q4)

Back to top

First completed : July 07, 2024

Last updated : July 07, 2024

Related Topics : Array, String, Dynamic Programming, Suffix Array

Acceptance Rate : 19.72 %

Did the contest live and got through Q1 & Q2 very quickly. When I saw Q3 however, I got really confused so I decided to just skip it for now. Somehow, I was able to get Q4 then when I got back to Q3, I realized what the solution was and laid out the steps, but didn't have enough time to implement it. So yeah... good contest lol. First time getting 3 questions too funny enough lol.

Version 1

Did a DP + String Comparison to get my solution. If this TLEed or MLEed, I would have changed to a DP + Trie solution to optimize the word == target[i:i+len(word)] portion. This, however, was unnecessary to pass the contest test cases, and so I moved onto another question as the contest was still active.

I do want to come back to this question and try the Aho–Corasick + DP solution.

Version 2

Tried adjusting for a DP + Trie solution and was successful. Overall time savings brought runtimes down from an average of 12300ms down to 11700ms, though only after additional tinkering. Next step, Aho-Corasick!

Notes from others

From Reddit:

The correct solution involves realizing that in if 
sum(len(w) for w in words) = M, then then are O(sqrt(M)) 
unique word lengths. Couple this with string hashing and 
you have an O(N * sqrt(M)) algorithm. 

...

Consider all the unique lengths as a list of length n. A 
lower bound of this is [1, 2, ..., n] with a total length 
of n(n+1)/2. Solving n(n+1)/2 = m gives n = O(sqrt(m))

Also, look into the potential for rolling hash solutions.

Solutions

Python

h3213 q4 v2 DP + Trie.py

class Solution:
    def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
        # Generate trie
        trie = {}
        for cost, word in zip(costs, words) :
            curr = trie
            for c in word :
                if c not in curr :
                    curr[c] = {}
                curr = curr[c]
            # If identical word exists, use smallest cost
            curr[False] = min(curr.get(False, inf), cost)

        # Dynamic Programming array
        dp = [0] + [inf] * len(target)

        # Iterate through each 
        for i in range(len(target)) :
            curr = trie
            offset = 0
            while i + offset < len(target) and target[i + offset] in curr  :
                curr = curr[target[i + offset]]
                offset += 1

                # Word ends
                if False in curr :
                    dp[i + offset] = min(dp[i + offset], dp[i] + curr[False])

        # -1 if end was not reachable
        return -1 if dp[-1] == inf else dp[-1]

h3213 q4.py

class Solution:
    def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
        wordToCost = Counter()
        for w, c in zip(words, costs) :
            # Always take the lowest cost case
            if w in wordToCost and wordToCost[w] <= c :
                continue
            wordToCost[w] = c

        # Remove duplicates from being checked
        words = sorted(set(words), key=lambda x: len(x))
        maxWrd = len(words) - 1

        dp = [0] + [inf] * len(target)

        for i in range(len(target)) :
            while maxWrd >= 0 and len(words[maxWrd]) > len(target) - i :
                maxWrd -= 1
            if maxWrd < 0 :
                break

            for word in words[:maxWrd + 1] :
                if word == target[i:i+len(word)] :
                    dp[i + len(word)] = min(dp[i + len(word)], dp[i] + wordToCost[word])

        return -1 if dp[-1] == inf else dp[-1]