Update 411.Minimum-Unique-Word-Abbreviation.cpp

wisdompeak · web-flow · commit 63f8056b8da7 · 2021-11-06T15:50:03.000-07:00
diff --git a/String/411.Minimum-Unique-Word-Abbreviation/411.Minimum-Unique-Word-Abbreviation.cpp b/String/411.Minimum-Unique-Word-Abbreviation/411.Minimum-Unique-Word-Abbreviation.cpp
@@ -1,83 +1,81 @@
 class Solution {
+    int m;
 public:
     string minAbbreviation(string target, vector<string>& dictionary) 
     {
         if (dictionary.size()==0)
-            return to_string(target.size());        
-                
-        unordered_set<string>Set;                
-        int N = target.size();
+            return to_string(target.size());
+        this->m = target.size();
         
-        for (auto str:dictionary)
+        unordered_set<string>Set;
+        for (auto word: dictionary)
         {
-            if (str.size()==N)
-                Set.insert(str);
-        }               
-                
-        vector<pair<int,int>>masks;        
-        for (int i=0; i<(1<<N); i++)        
-            masks.push_back({len(i,N),i});             
-        sort(masks.begin(),masks.end());
+            if (word.size()==m)
+                Set.insert(word);
+        }
+        
+        vector<pair<int,int>>masks;
+        for (int state = 0; state < (1<<m); state++)        
+            masks.push_back({len(state), state});
+        sort(masks.begin(), masks.end());
         
-        for (int i=0; i<masks.size(); i++)
+        for (auto x: masks)
         {
-            int mask = masks[i].second;
-            string a = abbr(target,mask);
+            int mask = x.second;
+            string abbr = getAbbr(target, mask);
             int flag = 1;
-                        
-            for (auto word:Set)
+            
+            for (auto word: Set)
             {
-                string b = abbr(word, mask);
-                if (a==b)
+                string s = getAbbr(word, mask);
+                if (s==abbr)
                 {
                     flag = 0;
                     break;
-                }
-            }            
-            if (flag == 1) return a;
+                }                
+            }
+            if (flag==1) return abbr;            
         }
-        return "";
+        
+        return "";        
     }
     
-    
-    int len(int mask, int N)
+    string getAbbr(string& word, int mask)
     {
-        int count = 0;
-        for (int i=0; i<N; i++)
+        string ret;
+        for (int i=0; i<m; i++)
         {
-            if (((mask>>i)&1)==1)        
-                count++;
+            if ((mask>>i)&1)
+                ret.push_back(word[i]);
             else
             {
-                int j = i+1;
-                while (j<N && ((mask>>j)&1)==0)
+                int j = i;
+                while (j<m && ((mask>>j)&1)==0)
                     j++;
-                count++;
+                ret  += to_string(j-i);
                 i = j-1;
             }
-        }        
-        return count;
+        }
+        return ret;
     }
     
-    string abbr(string A, int mask)
-    {       
-        string result;
-        int N = A.size();
-        
-        for (int i=0; i<N; i++)
+    int len(int mask)
+    {
+        int count = 0;
+        for (int i=0; i<m; i++)
         {
-            if (((mask>>i)&1)==1)
-                result.push_back(A[i]);
+            if ((mask>>i)&1)
+                count++;
             else
             {
-                int j = i+1;
-                while (j<N && ((mask>>j)&1)==0)
+                int j = i;
+                while (j<m && ((mask>>j)&1)==0)
                     j++;
-                result += to_string(j-i);
+                count += to_string(j-i).size();
                 i = j-1;
             }
         }
-        return result;
+        return count;
+        
     }
-    
 };
