471. Encode String with Shortest Length

SillyMonkey 发布于2019-08-14 17:28 / 593人阅读

摘要：题目链接这题还是有点难想的，一开始的思路想的还不对，参考这个博客的解释表示最短的压缩结果，里面枚举切分点，分别得到和求和，找到长度最短的。这道题关键是找这种可压缩的情况，其中。

471. Encode String with Shortest Length

题目链接：https://leetcode.com/problems...

这题还是有点难想的，一开始dp的思路想的还不对，参考这个博客的解释：http://www.cnblogs.com/grandy...

dpi表示s[i, j]最短的压缩结果，subproblem里面枚举切分点k，分别得到dpi和dpk+1求和，找到长度最短的。

这道题关键是找sub = abcabc这种可压缩的情况，其中sub = s[i,j]。方法比较巧妙，用sub+sub = abcabcabcabc，找第二个s在s+s里出现的位置，如果不是len(sub)，则说明sub有重复，那么就要压缩这个sub，重复次数是len(sub) / indexOf(sub, 1)，重复的string用的是之前压缩过的dpi，index = indexOf(sub, 1)。

public class Solution {
    public String encode(String s) {
        int n = s.length();
        String[][] dp = new String[n][n];
        for(int i = 0; i < n; i++) dp[i][i] = "" + s.charAt(i);
        // j - i
        for(int len = 1; len < n; len++) {
            for(int i = 0; i + len < n; i++) {
                int j = i + len;
                // enumerate seperate k
                for(int k = i; k < j; k++) {
                    int left = dp[i][k].length();
                    int right = dp[k+1][j].length();
                    // update shortest encoded string within (i, j)
                    if(dp[i][j] == null || left + right < dp[i][j].length()) {
                        dp[i][j] = dp[i][k] + dp[k+1][j];
                    }
                }
                // update string within (i, j), encode abcabc
                String sub = s.substring(i, j + 1);
                int index = (sub + sub).indexOf(sub, 1);
                if(index < sub.length()) {
                    sub = (sub.length() / index) + "[" + dp[i][i+index-1] + "]";
                }
                if(dp[i][j] == null || dp[i][j].length() > sub.length()) {
                    dp[i][j] = sub;
                }
            }
        }
        
        return dp[0][n-1];
    }
}

专线服务服务器托管 Shortest Length length属性 length值

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66661.html

Encode String with Shortest Length

Encode String with Shortest Length 题目链接：https://leetcode.com/problems...

kamushin233 2019-08-14 17:18 评论0 收藏0
[Leetcode] Shortest Word Distance 最短单词间距

摘要：代码第一次写入就先不比较第一次写入就先不比较哈希表法复杂度时间空间思路因为会多次调用，我们不能每次调用的时候再把这两个单词的下标找出来。我们可以用一个哈希表，在传入字符串数组时，就把每个单词的下标找出存入表中。 Shortest Word Distance Given a list of words and two words word1 and word2, return the ...

jsliang 2019-08-14 12:48 评论0 收藏0
[LeetCode] 244. Shortest Word Distance II

Problem Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the l...

Nekron 2019-08-16 14:00 评论0 收藏0
[LeetCode] 126. Word Ladder II

摘要：存放过程中的所有集合为所有的结尾，则顺序存放这个结尾对应的中的所有存放同一个循环的新加入的，在下一个循环再依次对其中元素进行进一步的把首个字符串放入新，再将放入，并将键值对放入，进行初始化 Problem Given two words (start and end), and a dictionary, find all shortest transformation sequenc...

wayneli 2019-08-14 14:27 评论0 收藏0
[LeetCode] 862. Shortest Subarray with Sum at Leas

摘要：较早放入的元素在队列顶部最近放入的元素在队列尾部检查最近放入的，保证队列中新放入的及对应的均为递增反证若保留，那么在下面第二个循环，该元素有可能中断循环，并使得我们无法得到队列更左边的最优解检查较早放入的最小距离 Problem Return the length of the shortest, non-empty, contiguous subarray of A with sum...

thursday 2019-08-16 13:50 评论0 收藏0