14 ms solution DFS with optimization


  • 2
    Q

    Assuming abbreviation only have k letters in it, where k range from 0 to target.length(). Check all the possible abbreviation against the dictionary in this situation and remember the one with minimal abbreviation count.
    But this is not correct, if we have '1' inside our abbreviation, the number doesn't reduce the abbreviation count against the situation when you have more letters in your abbreviation.

    Consider two abbreviations for target "apple": "a1p1e" and "app1e". If a1p1e is a valid abbreviation against our dictionary, so will app1e be. However, a1p1e will be check earlier than app1e since it has 3 characters in the abbreviation and this kind of abbreviation could also be longer than abbreviation sitting behind it in the loop.

    In order to optimize, that is to stop when enough, we can skip whenever we want to add a '1' into the abbreviation. It doesn't matter, The skipped situation can be checked later with more characters count in the abbreviation.

    Here is the code:
    aCnt is the abbreviation count
    cCnt is the characters count in abbreviation for the rest of the target string

    public class Solution {
        int len;
        public String minAbbreviation(String target, String[] dictionary) {
            len = target.length();
            StringBuilder sb = new StringBuilder();
             // k is the number of letters in result
            for (int k = 0; k < len; ++k) {        
                if (helper(target.toCharArray(), 0, len-1, sb, dictionary, k, new int[1])) {
                    // no need to keep on going anymore, the rest abbreviation will be longer
                    return sb.toString(); 
                }
                sb.setLength(0);
            }
            return target;    
        }
    
        private boolean helper(char[] tChars, int st, int ed, StringBuilder sb, String[] dictionary, int cCnt, int[] aCnt) {
            if (st > ed) {
                String ts = sb.toString();
                for (String s : dictionary) {
                    if (s.length() != len) {
                        continue;
                    }
                    if (validWordAbbreviation(s,ts)) {
                        return false;
                    }
                }
                return true;
            }
            if (cCnt == 0) {   // put no more letter, start checking
                sb.append(ed-st+1);
                aCnt[0]++;
                return helper(tChars, ed+1, ed, sb, dictionary, 0, aCnt);
            }
            String tMinStr = null;
            int tMinLen = Integer.MAX_VALUE;
            int tLen = sb.length();
            int tCnt = aCnt[0];
            for (int i = st; i <= ed; ++i) {
                if (i == st + 1) {  // skip when 1 is suppose to be inserted
                    continue;
                }
                if (ed-i < cCnt-1) {
                    break;
                }
                if (i - st > 0) {
                    aCnt[0]++;
                    sb.append(i-st);
                }
                aCnt[0]++;
                sb.append(tChars[i]);
                if (helper(tChars, i+1, ed, sb, dictionary, cCnt-1, aCnt)) {
                    if (aCnt[0] < tMinLen) {   // remember the minimal count result
                        tMinLen = aCnt[0];
                        tMinStr = sb.toString();
                    }
                }
                aCnt[0] = tCnt;
                sb.setLength(tLen);
            }
            if (tMinStr != null) {
                sb.setLength(0);
                sb.append(tMinStr);
                aCnt[0] = tMinLen;
                return true;
            }
            return false;
        }
        public boolean validWordAbbreviation(String word, String abbr) {
            char[] wChars = word.toCharArray();
            char[] aChars = abbr.toCharArray();
            int wIndex = 0, aIndex = 0;
            while (wIndex < wChars.length && aIndex < aChars.length) {
                if (aChars[aIndex] >= 'a' && aChars[aIndex] <= 'z') {
                    if (aChars[aIndex] != wChars[wIndex]) {
                        return false;
                    }
                    aIndex++;
                    wIndex++;
                } else if (aChars[aIndex] >= '1' && aChars[aIndex] <= '9') {
                    int adv = aChars[aIndex]-'0';
                    aIndex++;
                    while (aIndex < aChars.length && aChars[aIndex] >= '0' && aChars[aIndex] <= '9') {
                        adv *= 10;
                        adv += (aChars[aIndex++]-'0');
                    }
                    wIndex += adv;
                } else {
                    return false;
                }
            }
            return wIndex == wChars.length && aIndex == aChars.length;
        }    
    }

Log in to reply
 

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