LeetCode 3213: Construct String with Minimum Cost Solution
Master LeetCode problem 3213 (Construct String with Minimum Cost), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
3213. Construct String with Minimum Cost
Problem Explanation
Explanation:
To solve this problem, we can use dynamic programming. We will iterate through the target string and maintain a dynamic programming array dp to keep track of the minimum cost to form the substring ending at each index i. For each index i, we will consider adding each word from the words array and calculate the cost to form the substring ending at index i with that word. We will update dp[i] with the minimum cost.
The final answer will be dp[target.length() - 1] if it is not equal to Integer.MAX_VALUE, indicating that it is possible to form the target string with the given words. Otherwise, we return -1.
Algorithm:
- Initialize dp array with size equal to target.length().
- Initialize dp[0] as costs[i] if words[i] can form the first character of the target string, otherwise Integer.MAX_VALUE.
- Iterate from index 1 to target.length() - 1:
- For each index i, iterate through all words and calculate the cost to form the substring ending at index i with each word.
- Update dp[i] with the minimum cost calculated.
- Return dp[target.length() - 1] if it is not equal to Integer.MAX_VALUE, otherwise return -1.
Time Complexity:
The time complexity of this solution is O(n * m) where n is the length of the target string and m is the number of words.
Space Complexity:
The space complexity is O(n) where n is the length of the target string.
:
Solution Code
class Solution {
public int minCost(String target, String[] words, int[] costs) {
int n = target.length();
int[] dp = new int[n];
Arrays.fill(dp, Integer.MAX_VALUE);
for (int i = 0; i < words.length; i++) {
if (words[i].charAt(0) == target.charAt(0)) {
dp[0] = Math.min(dp[0], costs[i]);
}
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < words.length; j++) {
if (words[j].charAt(words[j].length() - 1) == target.charAt(i)) {
int prevCost = (i - words[j].length() >= 0) ? dp[i - words[j].length()] : 0;
dp[i] = Math.min(dp[i], prevCost + costs[j]);
}
}
}
return (dp[n - 1] != Integer.MAX_VALUE) ? dp[n - 1] : -1;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 3213 (Construct String with Minimum Cost)?
This page provides optimized solutions for LeetCode problem 3213 (Construct String with Minimum Cost) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 3213 (Construct String with Minimum Cost)?
The time complexity for LeetCode 3213 (Construct String with Minimum Cost) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 3213 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3213 in Java, C++, or Python.