2022-01-22：力扣411，最短独占单词缩写。
给一个字符串数组strs和一个目标字符串target。target的简写不能跟strs打架。
strs是[“abcdefg”,”ccc”]，target是”moonfdd”。target简写形式如果是”7″，会跟strs中的”abcdefg”打架，因为”abcdefg”简写形式也可以是”7″。target简写形式如果是”m6″，这就不会打架了，因为strs中没有以m开头，并且还有6个字符的字符串。
所以target的缩写就是”m6″。
答案2022-01-22：
递归。target的每个字符保留还是不保留。
字符串数组中跟目标字符串一样长的字符串，可以用位运算。比如”abcdefg”可以表示成0b111111，”moxnfdd”可以表示成0b0010000。相同为0，不同为1。
代码用golang编写。代码如下：
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)
}
// 区分出来之后，缩写的长度，最短是多少？
var min = math.MaxInt64
// 取得缩写的长度最短的时候，决定是什么(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
// 用来剪枝
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
}
}
}
// 原始的字典，被改了
// target : abc 字典中的词 : bbb -> 101 -> int ->
// fix -> int -> 根本不用值，用状态 -> 每一位保留还是不保留的决定
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
}
// 利用位运算加速
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
}
// 所有字典中的单词现在都变成了int，放在words里
// 0....len-1 位去决定保留还是不保留！当前来到index位
// 之前做出的决定!
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 {
// 决定是fix，一共的长度是len，求出缩写是多长？
ans := abbrLen(fix, len0)
if ans < min {
min = ans
best = fix
}
}
} 执行结果如下：
***
[左神java代码](
