-
Notifications
You must be signed in to change notification settings - Fork 22
/
Encode and Decode Strings.java
executable file
·151 lines (127 loc) · 4.37 KB
/
Encode and Decode Strings.java
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
M
1527968983
tags: String
如题.
#### String
- 'word.length()#word' 这样encode, 可以避免遇到#
- 基于我们自己定的规律, 在decode的里面不需要过多地去check error input, assume所有input都是规范的.
- decode就是找"#",然后用"#"前的数字截取后面的string.
```
/*
Design an algorithm to encode a list of strings to a string.
The encoded string is then sent over the network and is decoded back to the original list of strings.
Machine 1 (sender) has the function:
string encode(vector<string> strs) {
// ... your code
return encoded_string;
}
Machine 2 (receiver) has the function:
vector<string> decode(string s) {
//... your code
return strs;
}
So Machine 1 does:
string encoded_string = encode(strs);
and Machine 2 does:
vector<string> strs2 = decode(encoded_string);
strs2 in Machine 2 should be the same as strs in Machine 1.
Implement the encode and decode methods.
Note:
The string may contain any possible characters out of 256 valid ascii characters.
Your algorithm should be generalized enough to work on any possible characters.
Do not use class member/global/static variables to store states.
Your encode and decode algorithms should be stateless.
Do not rely on any library method such as eval or serialize methods.
You should implement your own encode/decode algorithm.
*/
/*
Use word.length() + "#" + word to mark a string. Append them all.
*/
public class Codec {
// Encodes a list of strings to a single string.
public String encode(List<String> strs) {
if (strs.size() == 0) {
return "";
}
StringBuffer sb = new StringBuffer();
for (int i = 0; i < strs.size(); i++) {
sb.append(strs.get(i).length() + "#" + strs.get(i));
}
return sb.toString();
}
// Decodes a single string to a list of strings.
public List<String> decode(String s) {
List<String> strs = new ArrayList<>();
if (s == null || s.length() == 0) {
return strs;
}
int start = 0;
while (start < s.length()) {
int ind = s.indexOf("#", start);
int leng = Integer.parseInt(s.substring(start, ind));
int end = ind + 1 + leng;
strs.add(s.substring(ind + 1, end));
start = end;
}
return strs;
}
}
/*
Thoughts:
Break into integers
Use some special words to: 1. break line. 2. record null condition.
Note: "" empty string is also a string case, so don't treat that as null. Call null, "NULL"
Note2: As long as the list is not empty, though some string might be just "", make sure to encode it as 'LINE' just to remind in decoder: treat it as a ""
*/
public class Codec {
// Encodes a list of strings to a single string.
public static String encode(List<String> strs) {
if (strs == null || strs.size() == 0) {
return "NULL";
}
StringBuffer sb = new StringBuffer();
for (String str : strs) {
char[] arr = str.toCharArray();
for (int i = 0; i < arr.length; i++) {
if (arr[i] >= 100) {
sb.append("" + (int)arr[i]);
} else if (arr[i] >= 10) {
sb.append("0" + (int)arr[i]);
} else {
sb.append("00" + (int)arr[i]);
}
}
sb.append("LINE");
}//END for
if (sb.length() == 0) {
sb.append("LINE");
}
return sb.toString();
}
// Decodes a single string to a list of strings.
public static List<String> decode(String s) {
List<String> rst = new ArrayList<String>();
if (s.equals("NULL")) {
return rst;
}
int index = s.indexOf("LINE");
while (index != -1) {
String str = s.substring(0, index);
StringBuffer sb = new StringBuffer();
int i = 0;
while (i + 3 <= str.length()) {
int letter = Integer.parseInt(str.substring(i, i + 3));
sb.append((char)letter);
i+=3;
}
rst.add(sb.toString());
s = s.substring(index + 4);
index = s.indexOf("LINE");
}
return rst;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(strs));
```