public class Codec {
// Encodes a list of strings to a single string.
public String encode(List<String> strs) {
StringBuilder sb = new StringBuilder();
for(String str : strs){
for(int i = 0; i < str.length(); i++){
if(str.charAt(i) == '#'){
sb.append('\\');
}
sb.append(str.charAt(i));
}
sb.append('#');
}
if(sb.length() > 1) sb.setLength(sb.length() - 1);
return sb.toString();
}
// Decodes a single string to a list of strings.
public List<String> decode(String s) {
List<String> list = new ArrayList<String>();
StringBuilder sb = new StringBuilder();
for(int i = 0; i < s.length(); i++){
if(s.charAt(i) != '#'){
sb.append(s.charAt(i));
} else {
// Found '\#' , remove '\' and add '#'
if(i - 1 >= 0 && s.charAt(i - 1) == '\\'){
sb.setLength(sb.length() - 1);
sb.append('#');
} else {
list.add(sb.toString());
sb.setLength(0);
}
}
}
if(sb.length() > 0){
list.add(sb.toString());
}
return list;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(strs));
思想上讲和 OS 的 file system 是非常像的，在实际 data 最前面的 header 里会存 metadata，告诉你下一段数据的内存地址或者offset。
public class Codec {
// Encodes a list of strings to a single string.
public String encode(List<String> strs) {
StringBuilder sb = new StringBuilder();
for(String str : strs){
sb.append(str.length());
sb.append(':');
sb.append(str);
}
return sb.toString();
}
// Decodes a single string to a list of strings.
public List<String> decode(String s) {
List<String> list = new ArrayList<String>();
int i = 0;
while(i < s.length()){
int delimiter = s.indexOf(':', i);
int size = Integer.valueOf(s.substring(i, delimiter));
list.add(s.substring(delimiter + 1, delimiter + 1 + size));
i = delimiter + 1 + size;
}
return list;
}
}
public class Codec {
// Encodes a list of strings to a single string.
public String encode(List<String> strs) {
StringBuilder sb = new StringBuilder();
for(String str : strs){
for(int i = 0; i < str.length(); i++){
char chr = str.charAt(i);
if(chr == '/'){
sb.append("//");
} else if(chr == '#'){
sb.append("/#");
} else {
sb.append(chr);
}
}
sb.append("#");
}
return sb.toString();
}
// Decodes a single string to a list of strings.
public List<String> decode(String s) {
List<String> res = new ArrayList<>();
StringBuilder str = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '/') {
str.append(s.charAt(++i));
} else if (s.charAt(i) == '#') {
res.add(str.toString());
str.setLength(0);
} else {
str.append(s.charAt(i));
}
}
return res;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(strs));
这题本身非常简单，但是写 sample test case 的人有点智障。。。得看着挂了的 test case 一点一点猜才能知道这题到底是想干啥。
public class ValidWordAbbr {
HashMap<String, String> map;
public ValidWordAbbr(String[] dictionary) {
map = new HashMap<String, String>();
for(String str:dictionary){
String key = getKey(str);
// If there is more than one string belong to the same key
// then the key will be invalid, we set the value to ""
if(map.containsKey(key)){
if(!map.get(key).equals(str)){
map.put(key, "");
}
} else {
map.put(key, str);
}
}
}
public boolean isUnique(String word) {
return !map.containsKey(getKey(word))||map.get(getKey(word)).equals(word);
}
String getKey(String str){
if(str.length() <= 2) return str;
return str.charAt(0)+Integer.toString(str.length()-2)+str.charAt(str.length()-1);
}
}
典型的搜索问题，对于 "word" ，该词的搜索图和状态空间如图所示：
第一遍 AC 的代码~
错误1：不能盲目用 indexOf(len) 去找下一个起点，因为 len 作为一个数字是可以重复的。
public class Solution {
public List<String> generateAbbreviations(String word) {
List<String> list = new ArrayList<>();
dfs(list, new StringBuilder(), word.toCharArray(), 0, 0);
return list;
}
private void dfs(List<String> list, StringBuilder sb, char[] word, int index, int curNum){
int len = sb.length();
if(index == word.length){
if(curNum != 0) sb.append(curNum);
list.add(sb.toString());
} else {
// Don't add, merge to current number
dfs(list, sb, word, index + 1, curNum + 1);
// Add current char
if(curNum != 0) sb.append(curNum);
dfs(list, sb.append(word[index]), word, index + 1, 0);
}
sb.setLength(len);
}
}
