0%

刷算法(3)-字符串的编码与解码

271.字符串的编码与解码

设计一个算法,可以将一个 字符串列表 编码成为一个 字符串。这个编码后的字符串是可以通过网络进行高效传送的,并且可以在接收端被解码回原来的字符串列表。

思路

猛一看题目很简单以为简单的拼接起来,中间加个分隔符就行了,但是输入字符串本身可能就是分隔符。所以必须还要加上长度信息,我们的加码方法是长度+”/“+字符串,比如对于”a”,”ab”,”abc”,我们就变成”1/a2/ab3/abc”,那么我们解码的时候就有规律可寻,先寻找”/“,然后之前的就是要取出的字符个数,从“/“后取出相应个数即可,以此类推直至没有”/“了。编码方法是这样,具体解码又以下三种思路。

解法1

用一个索引i来标记从哪一位开始搜索分隔符,搜索到之后截出来前面的长度信息,根据长度信息再截出来对应字符串。之后把i往后移,重新开始搜索分隔符。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package com.company;

import java.util.ArrayList;
import java.util.List;

public class Codec1 {
// Encodes a list of strings to a single string.
public String encode(List<String> strs) {
StringBuilder sb = new StringBuilder();
for (String item : strs) {
int length = item.length();
sb.append(length).append("/").append(item);
}
return sb.toString();
}

// Decodes a single string to a list of strings.
public List<String> decode(String s) {
List<String> result = new ArrayList<>();
int i = 0;
while (i < s.length()) {
int pos = s.indexOf('/', i);
int itemSize = Integer.parseInt(s.substring(i, pos));
int start = pos + 1;
int end = pos + itemSize + 1;
if (end <= s.length()) {
String item = s.substring(start, end);
result.add(item);
}
i = end;
}
return result;
}
}

解法2

和解法1类似,区别在于我们每次可以从原始输入s里把对应item截出来后重新赋值,之后从裁剪后的s继续遍历,直到s为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
package com.company;

import java.util.ArrayList;
import java.util.List;

public class Codec2 {
public String encode(List<String> strs) {
StringBuilder sb = new StringBuilder();
for (String item : strs) {
sb.append(item.length()).append("/").append(item);
}
return sb.toString();
}

public List<String> decode(String s) {
List<String> result = new ArrayList<>();
while (!s.isEmpty()) {
int pos = s.indexOf("/");
int itemSize = Integer.parseInt(s.substring(0, pos));
result.add(s.substring(pos + 1, pos + itemSize + 1));
s = s.substring(pos + itemSize + 1);
}
return result;
}
}

解法3

我们可以编码的时候通过Java里的换行符\n进行分割,读入时借助BufferReader逐行读取就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
package com.company;


import java.io.BufferedReader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.List;

public class Codec {
public String encode(List<String> strs) {
StringBuilder sb = new StringBuilder();
for (String item : strs) {
sb.append(item).append('\n');
}
return sb.toString();
}

public List<String> decode(String s) {
List<String> result = new ArrayList<>();
BufferedReader br = new BufferedReader(new StringReader(s));
String temp = null;
try {
while ((temp = br.readLine()) != null) {
result.add(temp);
}
} catch (Exception e) {

}
return result;
}
}

三种方法对比

解法 耗时 内存
解法1 7ms 39.3MB
解法2 15ms 39.8MB
解法3 23ms 38.7MB

以下为leetcode执行结果:
WX20190922-104129@2x.png

String基础操作

indexOf

从左往右查找第一次出现x的索引,如果不出现则返回-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* Returns the index within this string of the first occurrence of the
* specified substring.
*
* <p>The returned index is the smallest value <i>k</i> for which:
* <blockquote><pre>
* this.startsWith(str, <i>k</i>)
* </pre></blockquote>
* If no such value of <i>k</i> exists, then {@code -1} is returned.
*
* @param str the substring to search for.
* @return the index of the first occurrence of the specified substring,
* or {@code -1} if there is no such occurrence.
*/
public int indexOf(String str) {
return indexOf(str, 0);
}

其中indexOf(str, 0)原型如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* Returns the index within this string of the first occurrence of the
* specified substring, starting at the specified index.
*
* <p>The returned index is the smallest value <i>k</i> for which:
* <blockquote><pre>
* <i>k</i> &gt;= fromIndex {@code &&} this.startsWith(str, <i>k</i>)
* </pre></blockquote>
* If no such value of <i>k</i> exists, then {@code -1} is returned.
*
* @param str the substring to search for.
* @param fromIndex the index from which to start the search.
* @return the index of the first occurrence of the specified substring,
* starting at the specified index,
* or {@code -1} if there is no such occurrence.
*/
public int indexOf(String str, int fromIndex) {
return indexOf(value, 0, value.length,
str.value, 0, str.value.length, fromIndex);
}

fromIndex表示开始搜索的地方,是算在数的。

lastIndexOf

从最后面开始找第一次出现x的索引,索引位置还是从正向开始计算的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
* Returns the index within this string of the last occurrence of the
* specified substring. The last occurrence of the empty string ""
* is considered to occur at the index value {@code this.length()}.
*
* <p>The returned index is the largest value <i>k</i> for which:
* <blockquote><pre>
* this.startsWith(str, <i>k</i>)
* </pre></blockquote>
* If no such value of <i>k</i> exists, then {@code -1} is returned.
*
* @param str the substring to search for.
* @return the index of the last occurrence of the specified substring,
* or {@code -1} if there is no such occurrence.
*/
public int lastIndexOf(String str) {
return lastIndexOf(str, value.length);
}

/**
* Returns the index within this string of the last occurrence of the
* specified substring, searching backward starting at the specified index.
*
* <p>The returned index is the largest value <i>k</i> for which:
* <blockquote><pre>
* <i>k</i> {@code <=} fromIndex {@code &&} this.startsWith(str, <i>k</i>)
* </pre></blockquote>
* If no such value of <i>k</i> exists, then {@code -1} is returned.
*
* @param str the substring to search for.
* @param fromIndex the index to start the search from.
* @return the index of the last occurrence of the specified substring,
* searching backward from the specified index,
* or {@code -1} if there is no such occurrence.
*/
public int lastIndexOf(String str, int fromIndex) {
return lastIndexOf(value, 0, value.length,
str.value, 0, str.value.length, fromIndex);
}

总结:indexOf和lastIndexOf里第二个位置参数是参与搜索的。

substring

substring(int beginIndex, int endIndex)截取的是从beginIndex开始到endIndex-1的字符串,截出来的长度为endIndex-beginIndex。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* Returns a string that is a substring of this string. The
* substring begins at the specified {@code beginIndex} and
* extends to the character at index {@code endIndex - 1}.
* Thus the length of the substring is {@code endIndex-beginIndex}.
* <p>
* Examples:
* <blockquote><pre>
* "hamburger".substring(4, 8) returns "urge"
* "smiles".substring(1, 5) returns "mile"
* </pre></blockquote>
*
* @param beginIndex the beginning index, inclusive.
* @param endIndex the ending index, exclusive.
* @return the specified substring.
* @exception IndexOutOfBoundsException if the
* {@code beginIndex} is negative, or
* {@code endIndex} is larger than the length of
* this {@code String} object, or
* {@code beginIndex} is larger than
* {@code endIndex}.
*/
public String substring(int beginIndex, int endIndex) {
if (beginIndex < 0) {
throw new StringIndexOutOfBoundsException(beginIndex);
}
if (endIndex > value.length) {
throw new StringIndexOutOfBoundsException(endIndex);
}
int subLen = endIndex - beginIndex;
if (subLen < 0) {
throw new StringIndexOutOfBoundsException(subLen);
}
return ((beginIndex == 0) && (endIndex == value.length)) ? this
: new String(value, beginIndex, subLen);
}

参考