# brute force solution just check every possible abbreviation

• 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)
}

``````

• 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.

• 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();
}
}``````

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