2022-01-22: Li Kou 411, the abbreviation of the shortest exclusive word. Give a string number

2022-01-22： Power button 411, The shortest word abbreviation .

Give an array of strings strs And a target string target.target The abbreviation of cannot follow strs fight .

strs yes "abcdefg","ccc",target yes "moonfdd".target If the abbreviated form is "7", Will follow strs Medium "abcdefg" fight , because "abcdefg" The abbreviated form can also be "7".target If the abbreviated form is "m6", There will be no fighting , because strs There is no such thing as m start , And there is 6 Character string .

therefore target The abbreviation of is "m6".

answer 2022-01-22：

recursive .target Whether to keep or not keep every character of .

A string as long as the target string in the string array , You can use bit operations . such as "abcdefg" It can be expressed as 0b111111,"moxnfdd" It can be expressed as 0b0010000. Same as 0, Different for 1.

The code to use golang To write . The code is as follows ：

package main

import (
    "fmt"
    "math"
)

func main() {
    dictionary := []string{"abcdefd", "ccc"}
    target := "moonfdd"
    ret := minAbbreviation1(target, dictionary)
    fmt.Println(ret)
    ret = minAbbreviation2(target, dictionary)
    fmt.Println(ret)
}

//  After distinguishing , Length of abbreviation , What's the shortest time ？
var min = math.MaxInt64

//  Get the shortest length of abbreviations , Decide what it is (fix)
var best = 0

func minAbbreviation2(target string, dictionary []string) string {
    min = math.MaxInt64
    best = 0
    //char[] t = target.toCharArray();
    t := []byte(target)
    len0 := len(t)
    siz := 0
    for _, word := range dictionary {
        if len(word) == len0 {
            siz++
        }
    }
    words := make([]int, siz)
    index := 0
    //  For pruning 
    diff := 0
    for _, word := range dictionary {
        if len(word) == len0 {
            w := []byte(word)
            status := 0
            for j := 0; j < len0; j++ {
                if t[j] != w[j] {
                    status |= 1 << j
                }
            }
            words[index] = status
            index++
            diff |= status
        }
    }
    dfs2(words, len0, diff, 0, 0)
    builder := ""
    count := 0
    for i := 0; i < len0; i++ {
        if (best & (1 << i)) != 0 {
            if count > 0 {
                builder += fmt.Sprint(count)
            }
            builder += fmt.Sprintf("%c", t[i])
            count = 0
        } else {
            count++
        }
    }
    if count > 0 {
        builder += fmt.Sprint(count)
    }
    return builder
}

func dfs2(words []int, len0, diff, fix, index int) {
    if !canFix(words, fix) {
        if index < len0 {
            dfs2(words, len0, diff, fix, index+1)
            if (diff & (1 << index)) != 0 {
                dfs2(words, len0, diff, fix|(1<<index), index+1)
            }
        }
    } else {
        ans := abbrLen(fix, len0)
        if ans < min {
            min = ans
            best = fix
        }
    }
}

//  The original dictionary , Changed 
// target : abc   Words in the dictionary  : bbb   ->  101 -> int ->
// fix -> int ->  It's not worth it at all , State of use  ->  Every decision to keep or not to keep 
func canFix(words []int, fix int) bool {
    for _, word := range words {
        if (fix & word) == 0 {
            return false
        }
    }
    return true
}

func abbrLen(fix, len0 int) int {
    ans := 0
    cnt := 0
    for i := 0; i < len0; i++ {
        if (fix & (1 << i)) != 0 {
            ans++
            if cnt != 0 {
                if cnt > 9 {
                    ans += 2 - cnt
                } else {
                    ans += 1 - cnt
                }
            }
            cnt = 0
        } else {
            cnt++
        }
    }
    if cnt != 0 {
        if cnt > 9 {
            ans += 2 - cnt
        } else {
            ans += 1 - cnt
        }
    }
    return ans
}

//  Use bit operations to speed up 
func minAbbreviation1(target string, dictionary []string) string {
    min = math.MaxInt64
    best = 0
    t := []byte(target)
    len0 := len(t)
    siz := 0
    for _, word := range dictionary {
        if len(word) == len0 {
            siz++
        }
    }
    words := make([]int, siz)
    index := 0
    for _, word := range dictionary {
        if len(word) == len0 {
            w := []byte(word)
            status := 0
            for j := 0; j < len0; j++ {
                if t[j] != w[j] {
                    status |= 1 << j
                }
            }
            words[index] = status
            index++
        }
    }
    dfs1(words, len0, 0, 0)
    //StringBuilder builder = new StringBuilder();
    builder := ""
    count := 0
    for i := 0; i < len0; i++ {
        if (best & (1 << i)) != 0 {
            if count > 0 {
                builder += fmt.Sprint(count)
            }
            builder += fmt.Sprintf("%c", t[i])
            count = 0
        } else {
            count++
        }
    }
    if count > 0 {
        builder += fmt.Sprint(count)
    }
    return builder
}

//  All the words in the dictionary have now become int, Put it in words in 
// 0....len-1  Bit to decide whether to keep it or not ！ Now comes index position 
//  Previous decisions !
func dfs1(words []int, len0, fix, index int) {
    if !canFix(words, fix) {
        if index < len0 {
            dfs1(words, len0, fix, index+1)
            dfs1(words, len0, fix|(1<<index), index+1)
        }
    } else {
        //  The decision was fix, The total length is len, Find out how long the abbreviation is ？
        ans := abbrLen(fix, len0)
        if ans < min {
            min = ans
            best = fix
        }
    }
}

The results are as follows ：

picture

---

Zuo Shen java Code