Java BFS solution: from shortest to longest using heap


  • 1

    Similar to the bit manipulation idea, I use "*" to replace the a char in the target string.
    Then, we start with putting a string with all "******" which has length =1 into the heap.
    When pop, check whether it is an overlap with other words in the dictionary.
    If not, we get the result and return it. Otherwise, we generate the next abbr from current one by replacing "*" with a char of the target string.

    public class Solution {
        class Abbr{
            String abbr;
            int len;
            Abbr(String abbr, int len) {
                this.abbr = abbr;
                this.len = len;
            }
        }
        int abbrLength(String abbr){
            int ret = 0, star = 0;
            for (char c: abbr.toCharArray()){
                if (c >= 'a' && c <= 'z') {
                    ret += 1 + star;
                    star = 0;
                } else if (c=='*'){
                    star = 1;
                }
            }
            return ret+star;
        }
        
        class CompAbbr implements Comparator<Abbr> {
            public int compare(Abbr s1, Abbr s2){
                return Integer.compare( s1.len, s2.len );
            }
        }
        
        void generateAbbr(String str, String abbr, Set<String> visited, PriorityQueue<Abbr> q){
            char[] temp = abbr.toCharArray();
            for (int i=0; i<temp.length;i++){
                if (temp[i] == '*') {
                    temp[i] = str.charAt(i);
                    String next = new String(temp);
                    if (! visited.contains(next) ) {
                        q.offer( new Abbr(next, abbrLength(next) ) );
                        visited.add( next );
                    }
                    temp[i] = '*';
                }
            }    
        }
        
        boolean isConflict(String abbr, String str){
            for (int i=0; i<abbr.length(); i++){
                if ( abbr.charAt(i) != '*' &&  str.charAt(i) != abbr.charAt(i) ) return false;
            }
            return true;
        }
        String NumAbbr(String abbr){
            String ret="";
            int count=0;
            for (char c : abbr.toCharArray() ){
                if (c >='a' && c <='z') { 
                    if (count > 0) {
                        ret += count;
                        count=0;
                    }
                    ret+=c;
                } else {
                    count++;
                }
            }
            if (count > 0) ret += count;
            return ret;
        }
        public String minAbbreviation(String target, String[] dictionary) {
            Set<String> visited = new HashSet();
            PriorityQueue<Abbr> q = new PriorityQueue(1, new CompAbbr() );
            int len=target.length();
            String first = "";
            for (int i=0; i<len; i++) first+="*";
            q.offer(new Abbr(first, 1) );
            while (! q.isEmpty() ) {
                Abbr ab = q.poll();
                String abbr = ab.abbr;
                boolean conflict = false; 
                for (String word: dictionary) {
                    if ( (word.length() == len) && isConflict(abbr, word) ) { 
                        conflict = true;
                        break;
                    }
                }
                if (conflict) {
                    generateAbbr(target, abbr, visited, q);
                } else {
                    return NumAbbr(abbr);
                }
            }
            return null;
        }
    }
    

Log in to reply
 

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