Really simple and straightforward Java solution


  • 33
    C

    Make abbreviation for each word.
    Then, check each word, if there are some strings which have same abbreviation with it, increase the prefix.

        public List<String> wordsAbbreviation(List<String> dict) {
            int len=dict.size();
            String[] ans=new String[len];
            int[] prefix=new int[len];
            for (int i=0;i<len;i++) {
                prefix[i]=1;
                ans[i]=makeAbbr(dict.get(i), 1); // make abbreviation for each string
            }
            for (int i=0;i<len;i++) {
                while (true) {
                    HashSet<Integer> set=new HashSet<>();
                    for (int j=i+1;j<len;j++) {
                        if (ans[j].equals(ans[i])) set.add(j); // check all strings with the same abbreviation
                    }
                    if (set.isEmpty()) break;
                    set.add(i);
                    for (int k: set) 
                        ans[k]=makeAbbr(dict.get(k), ++prefix[k]); // increase the prefix
                }
            }
            return Arrays.asList(ans);
        }
    
        private String makeAbbr(String s, int k) {
            if (k>=s.length()-2) return s;
            StringBuilder builder=new StringBuilder();
            builder.append(s.substring(0, k));
            builder.append(s.length()-1-k);
            builder.append(s.charAt(s.length()-1));
            return builder.toString();
        }
    

  • 0
    L
    This post is deleted!

  • 1

    Brilliant! Tried 3 times and always got MLE for me...

    Python version based on your idea.

    class Solution(object):
        def wordsAbbreviation(self, dict):
            """
            :type dict: List[str]
            :rtype: List[str]
            """
            def shorten(word, idx):
                return word if idx > len(word) - 3 else \
                       word[:idx] + str(len(word)-1-idx) + word[-1]
                   
            res = [shorten(word, 1) for word in dict]
            pre = {word : 1 for word in dict}
            n = len(dict)
            for i in range(n):
                while True:
                    duplicate = [j for j in range(i, n) if res[i] == res[j]]
                    if len(duplicate) == 1: break
                    for k in duplicate:
                        pre[dict[k]] += 1
                        res[k] = shorten(dict[k], pre[dict[k]])
            return res
    

  • 0

    Smart! ckcz123@'s solution in C++

    class Solution {
    public:
        vector<string> wordsAbbreviation(vector<string>& dict) {
            vector<string> res(dict.size());
            vector<int> pre(dict.size());
            for (int i=0;i<dict.size();i++)
                res[i]=abbreviate(dict[i], pre[i]=1); // make abbreviation for each string
            for (int i=0;i<dict.size();i++) // check conflicts for every string
                while (true) {
                    set<int> dup;
                    for (int j=i+1;j<dict.size();j++) 
                        res[j].compare(res[i])==0?dup.insert({j}):(void)0; // if conflict, put into a set
                    if (dup.empty()) 
                        break;
                    dup.insert(i);
                    for (int k: dup)
                        res[k]=abbreviate(dict[k], ++pre[k]); // increase the prefix
                }
            return res;
        }
        
        string abbreviate(string s, int k) {
            return (k>=s.size()-2) ? s:s.substr(0,k)+to_string((s.size()-k-1))+s.back();
        }
    };
    

  • 2
    W

    I wrote a shorter version

    public List<String> wordsAbbreviation(List<String> dict) {
      String ans[] = new String[dict.size()];
      abbreviate(ans, dict, IntStream.range(0, ans.length).boxed().collect(Collectors.toList()), 1);
      return Arrays.asList(ans);
    }
    
    private void abbreviate(String[] ans, List<String> dict, List<Integer> idxs, int k) {
      Map<String, List<Integer>> map = new HashMap<>();
      idxs.forEach(idx -> map.computeIfAbsent(getAbbr(dict.get(idx), k), key -> new ArrayList<>()).add(idx));
      for (Entry<String, List<Integer>> entry : map.entrySet())
        if (entry.getValue().size() == 1) ans[entry.getValue().get(0)] = entry.getKey();
        else abbreviate(ans, dict, entry.getValue(), k + 1);
    }
    
    private String getAbbr(String s, int k) {
      return s.length() - k < 3 ? s : s.substring(0, k) + (s.length() - 1 - k) + s.charAt(s.length() - 1);
    }

  • 0
    S

    What's the runtime complexity?


  • 1
    Z

    The run time is O(m*n^2) for worst case. n is the length of dict, and m is the average length of word in dict.


  • 0
    P

    @zestypanda

    If assume " String.equals(String) " takes O(1) time, I think the time complexity is O(n^2) on average, am I right? (n is the length of dict) How does the O(m^2) come out? Thanks!


  • 0
    Z

    @perfecttt I have corrected it to O(m*n^2). I think both compare and makeAbbr take O(m) for each string. For example, aaaaaaaaba, aaaaaaaaba,aaaaaaaaca.


  • 0
    P

    @zestypanda

    The compare method such as equals will take O(m) time where m is the length of the string. But I think makeAbbr will only take O(1) time since it only uses sb.append() and s.substring().


  • 0
    Z

    @perfecttt Sorry I am not a Java user. In C++, when creating a new string, the time complexity is the length of new string. Even a simple copy is O(m).


  • 0
    H
    This post is deleted!

  • 1
    H

    @zestypanda
    I checked on the google again, the worst case of equals is O(m) not O(1), so the time complexity is still O(m^2 * n^2) , am I right?


  • 0
    G

    I think even in JAVA, the substring still takes O(m) instead of O(1). Have to copy char by char.
    For the equals(), it will also take O(m) because the comparison will compare char by char.
    So the total time complexity will be O(m * n ^ 2).


  • 0
    D

    good idea! Thanks!


  • 0
    G

    @hshshs35 +1. I dont understand why people think it's m n^2? From my understanding it should be:
    for .... // n
    while... //m, as prefix may be updated O(m) times
    for ... // n
    if (equals) ... // m


  • 0
    A

    I used a hashtable and made it O(n)

    class Solution {
        public List<String> wordsAbbreviation(List<String> dict) {
          
            int len=dict.size();
            String[] retv=new String[len];
            int[] prefix=new int[len];
            HashMap<String, ArrayList<Integer>> map = new HashMap<String, ArrayList<Integer>>();
            ArrayList<Integer> redo = new ArrayList<>();
            for(int i=0;i<len;i++)
                redo.add(i);
    
            while(redo.size()>0){
                for (int pos : redo) {
                    String abbr = makeAbbr(dict.get(pos), prefix[pos]+1);
                    prefix[pos] += 1;
                    if(!map.containsKey(abbr))
                        map.put(abbr, new ArrayList<Integer>());
                    map.get(abbr).add(pos);// make abbreviation for each string
                }
    
                redo.clear();
                for(String key  : map.keySet())
                    if(map.get(key).size()>1){
                        redo.addAll(map.get(key));
                        map.put(key, new ArrayList<Integer>());
                    }
            }
    
            for(String k : map.keySet()){
                if(map.get(k).size()==1){
                    int p = map.get(k).get(0);
                    retv[p] = k;
                }
            }
    
            return Arrays.asList(retv);
        }
        
        public String makeAbbr(String s, int k) {
            if (k>=s.length()-2) return s;
            StringBuilder builder=new StringBuilder();
            builder.append(s.substring(0, k));
            builder.append(s.length()-1-k);
            builder.append(s.charAt(s.length()-1));
            return builder.toString();
        }
        
    
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.