Use 408 Valid Word Abbreviation as subroutine


  • 0
    D

    We can exhaust all possible abbreviations in the dictionary, and add them into a set. However, that involves lots of exponential operations. By using leetcode 408 as a subroutine, we can eliminate those expensive calculations.

    public class Solution {
        public String minAbbreviation(String target, String[] dictionary) {
            if (target == null || target.length() == 0) {
                return "";
            }
            if (dictionary == null || dictionary.length == 0) {
                return Integer.toString(target.length());
            }
            List<Abbr> targetAbbrs = getAbbr(target);
            Collections.sort(targetAbbrs);
            for (Abbr targetAbbr : targetAbbrs) {
                boolean conflict = false;
                for (String word : dictionary) {
                    if (validWordAbbreviation(word, targetAbbr.str)) {
                        conflict = true;
                        break;
                    }
                }
                if (!conflict) {
                    return targetAbbr.str;
                }
            }
            return "";
        }
    
        private List<Abbr> getAbbr(String str) {
            if (str == null || str.length() == 0) {
                return new ArrayList<>();
            }
            List<Abbr> abbrs = _getAbbr(str);
            for (Abbr abbr : abbrs) {
                ridPrefix(abbr);
            }
            return abbrs;
        }
    
        private List<Abbr> _getAbbr(String str) {
            if (str == null || str.length() == 0) {
                return new ArrayList<>();
            }
            return __getAbbr(str, 0);
        }
    
        private List<Abbr> __getAbbr(String str, int index) {
            List<Abbr> ret = new ArrayList<>();
            if (index == str.length()) {
                ret.add(new Abbr());
                return ret;
            }
            List<Abbr> children = __getAbbr(str, index + 1);
            for (Abbr child : children) {
                Abbr case1 = new Abbr(child);
                ridPrefix(case1);
                case1.str = str.charAt(index) + case1.str;
                case1.len++;
                ret.add(case1);
                Abbr case2 = new Abbr(child);
                case2.prefix = 1 + (case2.prefix == null ? 0 : case2.prefix);
                ret.add(case2);
            }
            return ret;
        }
    
        private Abbr ridPrefix(Abbr abbr) {
            if (abbr.prefix != null) {
                abbr.str = Integer.toString(abbr.prefix) + abbr.str;
                abbr.prefix = null;
                abbr.len++;
            }
            return abbr;
        }
    
        class Abbr implements Comparable<Abbr> {
            Integer prefix;
            String str = "";
            int len;
            public int compareTo(Abbr abbr) {
                return this.len - abbr.len;
            }
            public Abbr() {}
            public Abbr(Abbr abbr) {
                this.prefix = abbr.prefix;
                this.str = abbr.str;
                this.len = abbr.len;
            }
        }
        
        public boolean validWordAbbreviation(String word, String abbr) {
            return validWordAbbreviation(word == null ? "" : word, 0, abbr == null ? "" : abbr, 0);
        }
        
        private boolean validWordAbbreviation(String str1, int index1, String str2, int index2) {
            if (index1 > str1.length()) {
                return false;
            }
            if (index1 == str1.length() && index2 == str2.length()) {
                return true;
            }
            if (index1 == str1.length() || index2 == str2.length()) {
                return false;
            }
            char ch2 = str2.charAt(index2);
            if (ch2 == '0') {
                return false;
            }
            if (Character.isLowerCase(ch2)) {
                return str1.charAt(index1) == ch2 ? validWordAbbreviation(str1, index1 + 1, str2, index2 + 1) : false;
            } else {
                int num = 0;
                while (index2 < str2.length() && Character.isDigit(ch2 = str2.charAt(index2))) {
                    num = num * 10 + (ch2 - '0');
                    index2++;
                }
                return validWordAbbreviation(str1, index1 + num, str2, index2);
            }
        }
    }
    

Log in to reply
 

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