brute force solution just check every possible abbreviation


  • 2
    W

    It is a brute force, that generate every possible abbreviation of the target, from length 1, and check it against the dictionary; it is not beautiful and efficient; post here for open discussion and improvement.

    
    func minAbbreviation(target string, dictionary []string) string {
    	for i := 1; i <= len(target); i++ {
    		abbr := abbreviation(target, i)
    		for _, x := range abbr {
    			valid := true
    			for _, dict := range dictionary {
    				if validWordAbbreviation(dict, x) {
    					valid = false
    					break
    				}
    			}
    			if valid {
    				return x
    			}
    		}
    	}
    	return ""
    }
    
    func abbreviation(str string, k int) []string {
    	if k == 0 {
    		return []string{""}
    	}
    	var res []string
    
    	if k == 1 {
    		res = append(res, strconv.Itoa(len(str)))
    		if len(str) == 1 {
    			res = append(res, str)
    		}
    		return res
    	}
    	checked := make(map[string]bool)
    	for i := 0; i < len(str); i++ {
    		x := str[i]
    		for a := 0; a < k; a++ {
    			b := k - 1 - a
    
    			if i == 0 && a != 0 {
    				continue
    			}
    
    			if i > 0 && a == 0 {
    				continue
    			}
    
    			if i == len(str)-1 && b != 0 {
    				continue
    			}
    			if i < len(str)-1 && b == 0 {
    				continue
    			}
    
    			for _, lx := range abbreviation(str[:i], a) {
    				for _, rx := range abbreviation(str[i+1:], b) {
    					sx := lx + string(x) + rx
    					if checked[sx] {
    						continue
    					}
    					checked[sx] = true
    					res = append(res, sx)
    				}
    			}
    		}
    	}
    	return res
    }
    
    func validWordAbbreviation(word string, abbr string) bool {
    	x := 0
    	for i := 0; i < len(abbr); i++ {
    		if abbr[i] >= '0' && abbr[i] <= '9' {
    			if x == 0 && abbr[i] == '0' {
    				return false
    			}
    			x = x*10 + int(abbr[i]-'0')
    			continue
    		}
    		if x >= len(word) {
    			return false
    		}
    		word = word[x:]
    		x = 0
    		if abbr[i] != word[0] {
    			return false
    		}
    		word = word[1:]
    	}
    
    	return x == len(word)
    }
    
    

  • 11
    Y

    Have same idea, but implemented in Java:

    1. Use the approach of “320. Generalized Abbreviation” to generate all abbreviations of “target”;
    2. Put all the abbreviations into a PriorityQueue according to the length of the abbreviations;
    3. With each abbreviation, check whether it’s an abbreviation of any word in the dictionary using the approach of “408. Valid Word Abbreviation”.

    Source code is not included here.


  • 3
    J

    A java implementation based on your idea:

    public class Solution {
        public class Abbreviation{
            public String abbr;
            public int len;
            
            public Abbreviation(String abbr, int len){
                this.abbr = abbr;
                this.len = len;
            }
        }
        
        public String minAbbreviation(String target, String[] dictionary) {
            if(dictionary.length == 0) return Integer.toString(target.length());
            PriorityQueue<Abbreviation> q = new PriorityQueue<Abbreviation>(new Comparator<Abbreviation>(){
               public int compare(Abbreviation a1, Abbreviation a2){
                   return a1.len - a2.len;
               } 
            });
            generateAbbrs(q, target, "", 0, 0, false);
            System.out.println(q.size());
            while(!q.isEmpty()){
                String abbr = q.poll().abbr;
                boolean notMatch = true;
                for(int i=0; i<dictionary.length; i++){
                    if(isValidAbbr(dictionary[i], abbr)){
                        notMatch = false;
                        break;
                    }
                }
                if(notMatch) return abbr;
            }
            return "";
        }
        
        private void generateAbbrs(PriorityQueue<Abbreviation> q, String target, String path, int start, int len, boolean prevAbbr){
            if(start == target.length()){
                q.offer(new Abbreviation(path, len));
                return;
            }
            generateAbbrs(q, target, path+target.charAt(start), start+1, len+1, false);
            if(!prevAbbr){
                for(int i=start; i<target.length(); i++){
                    String str = target.substring(start, i+1);
                    generateAbbrs(q, target, path+Integer.toString(str.length()), i+1, len+1, true);
                }
            }
        }
        
        private boolean isValidAbbr(String word, String abbr){
            int index = 0, i = 0;
            while(i < abbr.length()){
                if(!Character.isDigit(abbr.charAt(i))){
                    if(index >= word.length() || word.charAt(index) != abbr.charAt(i)) return false;
                    index++; i++;
                }else{
                    int start = i;
                    while(i < abbr.length() && Character.isDigit(abbr.charAt(i))) i++;
                    int number = Integer.parseInt(abbr.substring(start, i));
                    index += number;
                }
            }
            return index == word.length();
        }
    }

Log in to reply
 

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