820. Short Encoding of Words
A valid encoding of an array of words is any reference string s and array of indices indices such that:
- words.length == indices.length
- The reference string s ends with the ‘#’ character.
- For each index indices[i], the substring of s starting from indices[i] and up to (but not including) the next ‘#’ character is equal to words[i].
Given an array of words, return the length of the shortest reference string s possible of any valid encoding of words.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| class Solution { bool isContain(string& longer, string& shorter) { for(int i = longer.length() - shorter.length(), j = 0; i < longer.length(); i++, j++) { if(longer[i] != shorter[j]) return false; } return true; } public: int minimumLengthEncoding(vector<string>& words) { vector<bool> isIncluded(words.size(), false); int res = 0; for(int i = 0; i < words.size(); i++) { if(isIncluded[i]) continue; for(int j = i + 1; j < words.size(); j++) { if(isIncluded[j]) continue; if(isContain(words[i].length() > words[j].length() ? words[i] : words[j], words[i].length() > words[j].length() ? words[j] : words[i])) { isIncluded[words[i].length() > words[j].length() ? j : i] = true; } } if(!isIncluded[i]) res += words[i].length() + 1; }
return res; } };
|