0527 solved.

liuyubobobo · liuyubobobo · commit 78eed94512fd · 2022-06-14T22:13:44.000-07:00
diff --git a/0501-1000/0527-Word-Abbreviation/cpp-0527/CMakeLists.txt b/0501-1000/0527-Word-Abbreviation/cpp-0527/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.22)
+project(cpp_0527)
+
+set(CMAKE_CXX_STANDARD 14)
+
+add_executable(cpp_0527 main.cpp)
diff --git a/0501-1000/0527-Word-Abbreviation/cpp-0527/main.cpp b/0501-1000/0527-Word-Abbreviation/cpp-0527/main.cpp
@@ -0,0 +1,90 @@
+/// Source : https://leetcode.com/problems/word-abbreviation/
+/// Author : liuyubobobo
+/// Time   : 2022-06-14
+
+#include <iostream>
+#include <vector>
+#include <algorithm>
+
+using namespace std;
+
+
+/// Hash Map + Simulation
+/// Time Complexity: O(len * 26^2 + nlogn + n * len^2)
+/// Space Compelxity: O(len * 26^2 + n)
+class Solution {
+public:
+    vector<string> wordsAbbreviation(const vector<string>& words) {
+
+        int n = words.size();
+
+        vector<string> res(n, "");
+
+        vector<int> table[26][26][401];
+        for(int i = 0; i < n; i ++){
+            const string& word = words[i];
+            table[word[0] - 'a'][word.back() - 'a'][word.size()].push_back(i);
+        }
+
+        for(int first = 0; first < 26; first ++)
+            for(int last = 0; last < 26; last ++)
+                for(int len = 2; len <= 400; len ++){
+                    const vector<int>& v = table[first][last][len];
+                    if(v.empty()) continue;
+                    if(v.size() == 1){
+                        res[v[0]] = get_abbr(words[v[0]], 0);
+                        continue;
+                    }
+
+                    vector<pair<string, int>> data(v.size());
+                    for(int i = 0; i < v.size(); i ++) data[i] = {words[v[i]], v[i]};
+                    sort(data.begin(), data.end());
+
+                    for(int i = 0; i < data.size(); i ++){
+                        const string& word = data[i].first;
+                        int index = data[i].second;
+
+                        for(int prefix_len = 2;; prefix_len ++){
+                            bool ok1 = i - 1 < 0 || word.substr(0, prefix_len) != data[i - 1].first.substr(0, prefix_len);
+                            bool ok2 = i + 1 >= data.size() || word.substr(0, prefix_len) != data[i + 1].first.substr(0, prefix_len);
+                            if(ok1 && ok2){
+                                res[index] = get_abbr(word, prefix_len - 1);
+                                break;
+                            }
+                        }
+                        assert(res[index] != "");
+                    }
+                }
+        return res;
+    }
+
+private:
+    // [0...prefix_end_index] + num + last_character
+    string get_abbr(const string& s, int prefix_end_index){
+
+        string res = s.substr(0, prefix_end_index + 1);
+        int len = s.size() - (prefix_end_index + 2);
+        if(len) res += to_string(len);
+        res += s.back();
+
+        return res.size() < s.size() ? res : s;
+    }
+};
+
+
+void print_vec(const vector<string>& res){
+    for(const string& e: res) cout << e << ' '; cout << '\n';
+}
+
+int main() {
+
+    vector<string> words1 = {"like","god","internal","me","internet","interval","intension","face","intrusion"};
+    print_vec(Solution().wordsAbbreviation(words1));
+    // ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]
+
+    vector<string> words2 = {"abcdefg","abccefg","abcckkg"};
+    print_vec(Solution().wordsAbbreviation(words2));
+    // ["abcd2g","abccefg","abcckkg"]
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -553,7 +553,7 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 524 | [Longest Word in Dictionary through Deleting](https://leetcode.com/problems/longest-word-in-dictionary-through-deleting/) | [solution](https://leetcode.com/problems/longest-word-in-dictionary-through-deleting/solution/) | [C++](0501-1000/0524-Longest-Word-in-Dictionary-through-Deleting/cpp-0524/) | | |
 | 525 | [Contiguous Array](https://leetcode.com/problems/contiguous-array/) | [solution](https://leetcode.com/problems/contiguous-array/solution/) [题解](https://leetcode-cn.com/problems/contiguous-array/solution/lian-xu-shu-zu-by-leetcode/) | [C++](0501-1000/0525-Contiguous-Array/cpp-0525/) | | |
 | 526 | [Beautiful Arrangement](https://leetcode.com/problems/beautiful-arrangement/) | [solution](https://leetcode.com/problems/beautiful-arrangement/solution/) | [C++](0501-1000/0526-Beautiful-Arrangement/cpp-0526/) | | |
-| | | | | | |
+| 527 | [Word Abbreviation](https://leetcode.com/problems/word-abbreviation/) | [solution](https://leetcode.com/problems/word-abbreviation/solution/) | [C++](0501-1000/0527-Word-Abbreviation/cpp-0527/) | | |
 | 528 | [Random Pick with Weight](https://leetcode.com/problems/random-pick-with-weight/description/) | [solution](https://leetcode.com/problems/random-pick-with-weight/solution/) | [C++](0501-1000/0528-Random-Pick-with-Weight/cpp-0528/) | | |
 | 529 | [Minesweeper](https://leetcode.com/problems/minesweeper/) | [无] | [C++](0501-1000/0529-Minesweeper/cpp-0529/) | | |
 | 530 | [Minimum Absolute Difference in BST](https://leetcode.com/problems/minimum-absolute-difference-in-bst/description/) | [无] | | [Java](0501-1000/0530-Minimum-Absolute-Difference-in-BST/java-0530/src/) | |
