Java Solution Changed from Generalized Abbreviation and Valid Word Abbreviation


  • 1
    Y

    Thanks to many other posts in minimum unique word abbreviation, gengeneralized abbreviation, and valid word abbreviation.

    First let's see a possible solution for generalized abbreviation:

    public List<String> generateAbbreviations(String word) {
        List<String> ret = new ArrayList<>();
        dfs(word.toCharArray(), 0, new StringBuilder(), 0, ret);
        return ret; // count is the current abbreviation number
    }
    
    private void dfs(char[] word, int pos, StringBuilder sb, int count, List<String> ret){
        int sblen = sb.length();
        if(pos == word.length){
            if(count > 0) sb.append(count);
            ret.add(sb.toString());
            sb.setLength(sblen);
            return;
        }
        
        // choose to abbreviate current pos
        dfs(word, pos+1, sb, count+1, ret);
        
        // not to abbreviate current pos
        if(count > 0) sb.append(count);
        sb.append(word[pos]);
        dfs(word, pos+1, sb, 0, ret);
        sb.setLength(sblen);
    }
    

    Then let's see a valid word abbreviation solution:

    public boolean validWordAbbreviation(String word, String abbr) {
        char[] w = word.toCharArray();
        char[] a = abbr.toCharArray();
        int i = 0, j = 0, cnt = 0;
        while(i < w.length && j < a.length){
            while(j < a.length && Character.isDigit(a[j])){ 
                if(cnt == 0 && a[j] == '0') return false; // Here the case a0a and a10 need to be considered!!!
                cnt = cnt*10+a[j]-'0';
                j++;
            }
            i += cnt;
            cnt = 0; // reset
            if(i > w.length) return false;
            if(i == w.length || j == a.length) break;
            if(w[i] != a[j])  return false;
            i++; j++;
        }
        return i == w.length && j == a.length;
    }
    

    Then we use these two solutions into Minimum unique word abbreviation with several tricks:
    (1) Loop through the total number of letters used in the final abbreviation. As we know the more letters used, the longer (or equal) the final abbreviation is. Thus, whenever we found one solution in one loop, we can jump out of the loop.
    (2) However, there are cases "2l2" and "4e". Although they have the same number of letters but different length. Thus, we need to search for all cases for each total number of letters. Record a bestAbbr.
    (3) Thanks to posts here, one trick is to ignore the abbreviation with count 1. Another trick is to ignore words in the dictionary that do not have the same length.
    (4) Thanks to the post here, I learn many patterns.

    Here is my solution:

    /* loop through each valid abbreviation and check if this is 
     * a valid abbreviation for other ones. 
     * If not, then check if this is the minimum length abbreviation.
     */
    public String minAbbreviation(String target, String[] dictionary) {
        char[] targetarr = target.toCharArray();
        StringBuilder bestAbbr = new StringBuilder(target);
        for(int totalLetter = 0; totalLetter <= target.length(); totalLetter++){ // the total letters in the abbreviation
            StringBuilder sb = new StringBuilder(); 
            int totalAbbr = targetarr.length-totalLetter;
            dfs(targetarr, 0, sb, totalLetter, totalAbbr, 0, bestAbbr, dictionary);
            if(bestAbbr.length() != target.length()) return bestAbbr.toString();
        }
        return target;
    }
    
    private void dfs(char[] target, int pos, StringBuilder sb, int totalLetter, int totalAbbr, int curcnt, 
                         StringBuilder bestAbbr, String[] dictionary){
        int sblen = sb.length();
        if(pos == target.length){
            if(curcnt == 1) return;// not allow to be abbreviated to 1
            if(curcnt > 0) sb.append(curcnt);
            String abbr = sb.toString();
            boolean isvalid = !hasConflict(target.length, abbr, dictionary);
            if(isvalid && abbr.length() < bestAbbr.length()){
                bestAbbr.setLength(0); // cannot just set to new stringbuilder or the same stringbuilder!!!
                bestAbbr.append(sb);   // always check the best instead of return directly is for the case:
            }                          // 2l2 and 4e. 2l2 appears before 4e for the same totalLetter count.
            sb.setLength(sblen);
            return;
        }
        
        if(totalAbbr > 0){ // this pos can be abbreviated 
            dfs(target, pos+1, totalLetter, totalAbbr-1, curcnt+1, sb, bestAbbr, dictionary);
        }
        
        if(totalLetter > 0 && curcnt != 1){ // this pos can remain not abbreviated
            if(curcnt > 0) sb.append(curcnt);
            sb.append(target[pos]);
            dfs(target, pos+1, totalLetter-1, totalAbbr, 0, sb, bestAbbr, dictionary);
            sb.setLength(sblen);
        }
    }
    
    private boolean hasConflict(int targetLen, String abbreviation, String[] dictionary){
        char[] abbr = abbreviation.toCharArray();
        for(String word: dictionary){
            if(targetLen != word.length()) continue; // trick(1)
            boolean isvalid = isValidAbbrOf(abbr, word.toCharArray());
            if(isvalid) return true;
        }
        return false;
    }
    
    private boolean isValidAbbrOf(char[] abbr, char[] word){
        int i = 0, j = 0, cnt = 0;
        while(i < abbr.length && j < word.length){
            while(i < abbr.length && Character.isDigit(abbr[i])){
                cnt = cnt*10 + abbr[i]-'0';
                i++;
            }
            // is letter
            j += cnt;
            cnt = 0;
            if(i == abbr.length || j >= word.length) break; // need to check both i and j
            if(abbr[i] != word[j]) return false;
            i++; j++;
        }
        return i == abbr.length && j == word.length;
    }

Log in to reply
 

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