2022-01-22：力扣411，最短独占单词缩写。 给一个字符串数组strs和一个目标字符串target

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代码