单词压缩编码问题（LeetCode）的笨方法以及由此产生的String类型陷阱再复习

逃离我推掉我的手 2023-07-18 14:16 4阅读 0赞

首先，题目是这样的：

给定一个单词列表，我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。

例如，如果这个列表是 \[“time”, “me”, “bell”\]，我们就可以将其表示为 S = “time\#bell\#” 和 indexes = \[0, 2, 5\]。

对于每一个索引，我们可以通过从字符串 S 中索引的位置开始读取字符串，直到 “\#” 结束，来恢复我们之前的单词列表。

那么成功对给定单词列表进行编码的最小字符串长度是多少呢？

示例：  
输入: words = \[“time”, “me”, “bell”\]  
输出: 10  
说明: S = “time\#bell\#” ， indexes = \[0, 2, 5\] 。

提示：  
1 <= words.length <= 2000  
1 <= words\[i\].length <= 7  
每个单词都是小写字母 。

## 解法一 ##

##### 对于这个题目，也就是要看这些单词之间，有没有存在类似于me和time这种，末尾一样，并且一个是另一个的子字符串的情况；然而tim和time却是不可以的，因为如果tim省略，没有\#标志的出现，是无法用索引表来找到这个词语的。 #####

##### 既然是末尾一样的情况才可以省略相较之下短的单词，正好利用substring方法的一个参数的情况：两个参数的是\[ )删除，一个参数是从该位置到字符串末尾删除。 #####

#### 同时Hashset有个特点remove的元素不在set里面的话，是不会删除内容的。 ####

class Solution {
        public int minimumLengthEncoding(String[] words) {
            Set<String> set = new HashSet<>(Arrays.asList(words));
            for (String word : words) {
                for (int i = 1; i < word.length(); i++) {
                    set.remove(word.substring(i));
                }
            }
            //System.out.println(set);
            int ans = 0;
            for (String word : set) {
                ans += word.length() + 1;
            }
            return ans;
        }
    }

## 解法二 ##

##### 既然判断子字符串的时候要从最后面对齐，那么干脆直接把每个字符串都倒序，然后排序，这样只需两两进行比较然后不断删除就可以了。 #####

然后写出了这样的代码：

class Solution {
        public int minimumLengthEncoding(String[] words) {
            for(String word:words){
                StringBuffer sb=new StringBuffer(word).reverse();
                word=sb.toString();//**注意这一句**
            }
            Arrays.sort(words);
            int sum=0;//总长度
            for(int i=0;i<words.length-1;i++){
                if(words[i]==words[i+1].substring(0,words[i].length())){//**以及这一句**
                    continue;//如果第i个是第i+1个的子字符串，就继续看下一个
                }
                sum+=words[i].length()+1;//words[i]的长度加上#
            }
            return sum+words[words.length-1].length()+1;//最后一个单词的长度要单独加上
        }
    }

### 然后报错了，并且问题漏洞非常大，我开始并没有意识到。 ###

我是这么分析的：报错的是在下面最后判断第i个是否为第i+1个的子字符串的时候，越界了。也就是说，从第i+1个单词的长度小于第i个才会出现这种情况，求substring出现越界。

我打算先测试一下sort方法对于字符串的排序情况（我的预计是按字母顺序，以及长度从短到长）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw_size_16_color_FFFFFF_t_70]  
这是java6的API文档里面的sort方法，上面还有一个byte类型的没截进来（总共有重载的18个sort方法），对于byte、char、double、float、int、long、short来说，都是对应了2个，一个是传入一个数组，按照升序排序，另外一个是指定范围进行排序，也就是指定数组的下标，比较简单。

剩下四个就是分别为：

*  1、public static void sort(Object\[\] a)根据元素的自然顺序对指定对象数组按升序进行排序。数组中的所有元素都必须实现Comparable接口。此外，数组中的所有元素都必须是 可相互比较的（也就是说，对于数组中的任何 e1 和 e2 元素而言， e1.compareTo(e2) 不得抛出 ClassCastException）。  
    保证此排序是稳定的：不会因调用 sort 方法而对相等的元素进行重新排序。  
    该排序算法是一个经过修改的合并排序算法（其中，如果低子列表中的最高元素小于高子列表中的最低元素，则忽略合并）。此算法提供可保证的 n\*log(n) 性能。参数：a - 要排序的数组抛出：ClassCastException - 如果数组包含不 可相互比较的 的元素（例如，字符串和整数）
 *  2、1对应的有范围限制的方法；
 *  3、public static void sort(T\[\] a,  
    Comparator<? super T> c)  
    根据指定比较器产生的顺序对指定对象数组进行排序。数组中的所有元素都必须是通过指定比较器 可相互比较的（也就是说，对于数组中的任何 e1 和 e2 元素而言， c.compare(e1, e2) 不得抛出 ClassCastException）。  
    保证此排序是稳定的：不会因调用 sort 方法而对相等的元素进行重新排序。  
    该排序算法是一个经过修改的合并排序算法（其中，如果低子列表中的最高元素小于高子列表中的最低元素，则忽略合并）。此算法提供可保证的 n\*log(n) 性能。  
    参数：  
    a - 要排序的数组  
    c - 确定数组顺序的比较器。 null 值指示应该使用元素的 自然顺序。  
    抛出：  
    ClassCastException - 如果数组包含使用指定的比较器不 可相互比较的 的元素。
 *  4、3对应的有范围限制的方法

由于我用到的是字符串数组，所以第一个方法需要关注。  
这里面我们先要看看Comparable接口，这个接口有很多实现类，意思就是说当传入一个Object类型的数组，这里面的各个元素都要是实现了comparable接口的类的对象，否则就会报错。也就意味着，比如整数可以排序，String可以排序，但如果你自定义了一个Student类，里面有int和String成员，这种对象，调用sort方法，他就会不知道该用哪个东西进行排序。如果你想要这么做，就得实现Comparable接口，复写里面的compareTo方法。

接着我来测试一下，sort一组字符串：

String[] s1=new String[]{"e","b","a","d","e"};
          Arrays.sort(s1);

输出了“abdee”，可以看到是按照字母顺序排序了，那么对于字符串的长度呢

String[] s2=new String[]{"aa","aab","a","b","bc"};

输出了“a aa aab b bc”

##### 我又换了几组，输出都是每个短到长并且按照字典顺序排序的，说明字符串类内部的compareTo是按照字典排序实现的。 #####

#### 到这里我突然发现，既然有aab完了是b这种情况，那么，== 越界难道不正常吗？？？？== ####

所以应该是使用的subString的参数有问题。由于substring方法本身的substring(int beginIndex,int endIndex)， 如果 beginIndex 为负，或 endIndex 大于此 String 对象的长度，或 beginIndex 大于 endIndex就会抛出异常。

##### 可是既然这时候单词已经倒置过后排好序了，所以只需要正常判断是不是第二个的子字符串，这个操作可以采用indexOf来判断，如果不是子字符串，就会返回-1，因此比用substring更方便；或者用后一个字符串是否以前一个字符串为开头，也可以，startsWith方法也不会抛出异常。 #####

更改之后，不报错了，可是结果是错的。

##### 卡住的测试用例是\[“time”, “atime”, “btime”\]，先翻转emit，emita，emitb，排序后再操作，没有问题压？ #####

这时候我去分步输出了一下，发现了一个致命的错误，那就是reverse操作后，数组并没有改变。

错误的重点原来在这里！！！！

### java的String是引用类型，更改值的实质是创建新的String，那么原来的数组里面的字符串有变化吗？没有！！！！ ###

### String类一经初始化，就不可能再改变值了，对他的操作都是对副本的操作，其实原来字符串没有发生改变。 ###

是不是很刺激！！！  
因此在倒置这一步用了一个新的字符串重新存储起来

class Solution {
        public int minimumLengthEncoding(String[] words) {
            String[] words2=new String[words.length];
            for(int i=0;i<words.length;i++){
                StringBuffer sb=new StringBuffer(words[i]).reverse();
                words2[i]=sb.toString();
            }
            Arrays.sort(words2);
            for(String word:words2) {
                System.out.print(word);
            }
            System.out.println();
            int sum=0;
            for(int i=0;i<words2.length-1;i++){
                if(words2[i+1].indexOf(words2[i])!=-1){
                    continue;//如果第i个是第i+1个的子字符串，就继续看下一个
                }
                sum+=words2[i].length()+1;//words[i]的长度加上#
            }
            return sum+words2[words2.length-1].length()+1;//最后一个单词的长度要单独加上
        }
    }

### 前面已经说了String类的问题，如果一直进行操作，就会产生大量副本的字符串对象存留在内存中，降低效率，极大影响程序运行时间和空间性能，甚至会造成服务器崩溃。因此优化的过程，就应该选择StringBuilder类来进行判断和最后的遍历。 ###

总算是结束了这道题，虽然效率不高，内存也挺惨，总算是过去了。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw_size_16_color_FFFFFF_t_70]: /images/20230528/22ad1052472f47a7848834d2d7c4078d.png