2746. 字符串连接删减字母 (opens new window)

1.记忆化搜索+回溯+递归

注意题干。每次合并操作需要顺序执行，依次连第1，2...n个字符串(如果是乱序执行连接操作，那么还需要枚举插入位置/下一个选择连接的字符串)。

按顺序选择需要连接的字符串，每个字符串只有两种操作方案：①插在已有串的首部②插在已有串的尾部。因此很容易想到使用深搜。而单纯的深搜不进行剪枝会直接超时。

因此本题的难点在于如何剪枝，而当前节点要想剪枝就需要思考什么情况下可以停止继续往下搜索？

• words = ["cb","ac","a","ca","a","abb","a","caa","aa"]

• dfs(index,head,tail)表示本次搜索需要将字符串words[index]进行合并，其中0到index-1之间字符串合并得到的当前串首字符head，尾字符tail。

可以发现树高为4的节点上，出现了长度不同但是首尾字符相同的字符串，它们往下搜索扩展得到的孩子节点肯定是相同的。因此这就启发我们剪枝的对象就是同一层首尾字符相同的节点。也就是说得到的当前串“acbca”可以利用前面“acbaca”的结果，不需要继续往下搜索。

而这里利用的“结果”具体是什么？显然acbca既然不想往下遍历，并且题目本身要求最短长度作为结果，那么从acbaca那里得到的只能是索引从4到words.length-1所有字符串与当前串axxxxxxa合并后增加的长度(不包括axxxxxa的长度)，并且是经过首尾消除得到的最小长度。从而最终长度res=length(acbca)+minMergeLength(index=4,5,...words.length-1)。

因为父节点需要获取子节点的长度结果，所以需要设置函数返回值为子节点的最短长度。即把len+dfs()返回return给父节点的递归写法。

记忆化搜索Map中，存储的key为head+tail+index拼接成的字符串，value为index~words.length-1后面字符串拼接得到的最短长度。具体来说：

• map中存在剩余合并串起点为index，当前合并串头尾元素为head和tail的节点最小长度，则取出并返回。
• 否则计算最小长度=len(words[index])+ 以index+1作为起点的剩余合并最小长度

✨记忆化搜索map的核心在于，当前节点如何利用其它已经搜索过的节点的结果。

class Solution {
    int res=Integer.MAX_VALUE;
    public int minimizeConcatenatedLength(String[] words) {
        Map<String,Integer> map=new HashMap<>();
        if(words.length==1) return words[0].length();
        return dfs(words[0].charAt(0),words[0].charAt(words[0].length()-1),words,map,1)+words[0].length();
    }
    public int dfs(Character head,Character tail,String[] words,Map<String,Integer> map,int index){
        String strkey=String.valueOf(head)+String.valueOf(tail)+String.valueOf(index);
        if(index==words.length-1){
            int len=words[index].length();
            if(words[index].charAt(0)==tail||words[index].charAt(words[index].length()-1)==head) len--;
            map.put(strkey,len);
            return len;
        }
        if(map.containsKey(strkey)) return map.get(strkey);
        //后插
        int back=words[index].length();
        if(words[index].charAt(0)==tail) back--;
        back+=dfs(head,words[index].charAt(words[index].length()-1),words,map,index+1);
        //前插
        int forward=words[index].length();
        if(words[index].charAt(words[index].length()-1)==head)forward--;
        forward+=dfs(words[index].charAt(0),tail,words,map,index+1);
        //放入缓存
        int minlen=Math.min(back,forward);
        map.put(strkey,minlen);
        return minlen;
        
    }
}