A valid encoding of an array of
words is any reference string
s and an array of indices
indices such that:
words.length == indices.length
- The reference string
sends with the
- For each index
indices[i], the substring of
indices[i]and up to (but not including) the next
'#'character is equal to
Given an array of
words, return the length of the shortest reference string
s possible of any valid encoding of
Input: words = ["time", "me", "bell"]
Explanation: A valid encoding would be s = "time#bell#" and indices = [0, 2, 5].
words = "time", the substring of s starting from indices = 0 to the next '#' is underlined in "time#bell#"
words = "me", the substring of s starting from indices = 2 to the next '#' is underlined in "time#bell#"
words = "bell", the substring of s starting from indices = 5 to the next '#' is underlined in "time#bell#"
Input: words = ["t"]
Explanation: A valid encoding would be s = "t#" and indices = .
1 <= words.length <= 2000
1 <= words[i].length <= 7
words[i]consists of only lowercase letters.
According to the question, we have to encode the given strings into one string that contains all the words from the given array of strings. It should be done in such a way that, we can minimize the length of the output string. Overlapping a string over another is allowed. Also after each string, we have to append
# to it.
Let's go through the algorithm for this problem. Here we have used a
Hashset to save all the given strings. We will check for overlapping of characters of words, if there is any overlapping of characters we delete that string. (This step can be better understood with the example). At last, we append the strings present in the
Hashset and add
# to it.
The code is given below.
If n is the length of the array of strings and k is the length of the longest string then
Time complexity: O(n*k)
Space complexity: O(n)
The code can be found in the following repository.
I have posted all the previous problems for the March LeetCoding Challenge 2021. You can check them out.