Solution 1: Brute Force + HashSet

Try all possible substrings

Time complexity: O(n^3)
Space complexity: O(n^2)

C++

// Author: Huahua

class Solution {

public:

int distinctEchoSubstrings(string text) {

const int n = text.length();

string_view t(text);

unordered_set<string_view> s;

for (int k = 1; k <= n / 2; ++k)

for (int i = 0; i + k <= n; ++i)

if (t.substr(i, k) == t.substr(i + k, k))

s.insert(t.substr(i, 2 * k));

return s.size();

}

};

Problem

Given a list of words, we may encode it by writing a reference string S and a list of indexes A.

For example, if the list of words is ["time", "me", "bell"], we can write it as S = "time#bell#" and indexes = [0, 2, 5].

Then for each index, we will recover the word by reading from the reference string from that index until we reach a “#” character.

What is the length of the shortest reference string S possible that encodes the given words?

Example:

Input: words = ["time", "me", "bell"] Output: 10 Explanation: S = "time#bell#" and indexes = [0, 2, 5].

Note:

1 <= words.length <= 2000.
1 <= words[i].length <= 7.
Each word has only lowercase letters.

Idea

Remove all the words that are suffix of other words.

Solution

Time complexity: O(n*l^2)

Space complexity: O(n*l)

// Author: Huahua

// Running time: 43 ms

class Solution {

public:

int minimumLengthEncoding(vector<string>& words) {

unordered_set<string> s(words.begin(), words.end());

for (const string& w : words) {

for (int i = w.length() - 1; i > 0; --i)

s.erase(w.substr(i));

}

int ans = 0;

for (const string& w : s)

ans += w.length() + 1;

return ans;

}

};

Posts tagged as “hashset”

花花酱 LeetCode 1316. Distinct Echo Substrings

Solution 1: Brute Force + HashSet

C++

花花酱 LeetCode 820. Short Encoding of Words

Problem

Idea

Solution