Encode and Decode Strings
BitTorrent 有一个P2P跨平台的序列化规范，简单易懂，叫Bencode, 简单讲就是 “长度 + 分隔符 + 字符串” 的 encoding.
思想上讲和 OS 的 file system 是非常像的，在实际 data 最前面的 header 里会存 metadata，告诉你下一段数据的内存地址或者offset。
// Encodes a list of strings to a single string.
public String encode(List<String> strs) {
StringBuilder sb = new StringBuilder();
for(String s: strs){
sb.append(s.length()+"/"+s);
}
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(s);
while(sb.length()>0){
int index = sb.indexOf("/");
int len = Integer.valueOf(sb.substring(0, index));
list.add(sb.substring(index+1, index+1+len));
sb = new StringBuilder(sb.substring(index+1+len));
}
return list;
}
}
Escape符的正确定义是：看到了就跳过，但是 escape 符后面的一定是有效字符。
于是一个落单的 '#' 代表单词 delimiter ;
原字符串的 '#' 变成了 '/ + #'；这样保证可以加进去但是又不会作为 '#' 单独被判断；
原字符串的 '/' 就变成了 '//'，实际意义是 "escape 符 + 有效字符"。
System.out.println("\"); output: \
在序列化多叉树的时候就可以允许特殊字符的存在.
犯错一: Escape 符号decode完后要自增1, if(sb.charAt(i)=='/') tmp.append(sb.charAt(i++));
// Encodes a list of strings to a single string.
public String encode(List<String> strs) {
StringBuilder sb = new StringBuilder();
for(String s : strs){
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='/'){
sb.append("//");
}
else if(s.charAt(i)=='#'){
sb.append("/#");
}
else
sb.append(s.charAt(i));
}
sb.append("#");
}
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(s);
StringBuilder tmp = new StringBuilder();
System.out.println(sb.toString());
for(int i=0;i<sb.length();i++){
if(sb.charAt(i)=='/'){
tmp.append(sb.charAt(i+1));
i++;
}
else if(sb.charAt(i)=='#'){
list.add(tmp.toString());
tmp.setLength(0);
}
else
tmp.append(sb.charAt(i));
}
return list;
}
}
Unique Word Abbreviation
这题本身非常简单，但是写 sample test case 的人有点智障。。。得看着挂了的 test case 一点一点猜才能知道这题到底是想干啥。
这题的意思是，我们要看的是一个 key 到底是否有效； 给你一个 word，如果字典里面完全没有一样的 abbreviation -> true; 如果有一样的 abbreviation 但是全和你的 word 是一样的单词，也返回 true；其他的都是 false;
注意当dictionary里有两个词有一样的缩写的时候,set value 为空. 当查询key的时候一定返回false.
public class ValidWordAbbr {
HashMap<String, String> map;
public ValidWordAbbr(String[] dictionary) {
map = new HashMap<String, String>();
for(String s : dictionary){
String key = getKey(s);
if(map.containsKey(key)){
if(!map.get(key).equals(s))
map.put(key, "");
}
else{
map.put(key,s);
}
}
}
public String getKey(String s){
if(s.length()<=2)
return s;
return s.charAt(0)+ Integer.toString(s.length()-2) +s.charAt(s.length()-1);
}
public boolean isUnique(String word) {
String key = getKey(word);
return !map.containsKey(key) || map.get(key).equals(word);
}
}
// Your ValidWordAbbr object will be instantiated and called as such:
// ValidWordAbbr vwa = new ValidWordAbbr(dictionary);
// vwa.isUnique("Word");
// vwa.isUnique("anotherWord");
Generalized Abbreviation
典型的搜索问题，对于 "word" ，该词的搜索图和状态空间如图所示：
第一遍 AC 的代码~
错误1：不能盲目用 indexOf(len) 去找下一个起点，因为 len 作为一个数字是可以重复的。
错误2：用 lastIndexOf 也不行，因为数字不都是一位数，有肯能会出现重复数字的两位数。
因此， 最稳的做法是，pos 一定新 string 的起点，然后加上数字 string 的长度，再加一。
public class Solution {
public List<String> generateAbbreviations(String word) {
List<String> result = new ArrayList<String>();
helper(word, 0, 0, "",result);
return result;
}
public void helper(String word, int start, int count, String cur, List<String> result){
if(start==word.length()){
if(count>0)
cur+=count;
result.add(cur);
return;
}
helper(word, start+1, count+1, cur, result);
helper(word, start+1, 0, cur+ (count>0?count:"")+word.charAt(start), result);
}
}
(Google)字符串嵌套压缩 / 解压缩
变种1：
Decode String
http://www.1point3acres.com/bbs/thread-189365-1-1.html
上来大概问了5分钟background然后直接上题，一个string decompression的题。。不知道是不是原题反正没见过。。题目如下.
2[abc]3[a]c => abcabcabcaaac; 2[ab3[d]]2[cc] => abdddabdddcc 输入 输出 一开始用了一个栈，写着写着嵌套的逻辑卡住了，最后用俩stack解决。。然后follow-up问的是不要输出string而是输出解压后的K-th character，主要也还是嵌套情况就从内到外把疙瘩解开以后再算。。然后我问俩问题就结束了。整体感觉妹子面试官人很nice 反应很快而且不是特别picky的那种。
变种2：
“3a2[mtv]ac”, decompress to: aaamtvmtvac，括号可以嵌套。 这个我觉得不是很难，大概花了15分钟理清了思路并写好了代码，大概就是找匹配括号递归解，面试官也找不到bug表示认同。
但吊诡的地方来了，面试官说把这种字符串compress回去...这显然有多种情况，于是我问是不是要求压缩后最短，面试官说肯定越短越好。 比如对于aaaa, 肯定4a比2[aa]好。
Encode String with Shortest Length
Input: "abbbabbbcabbbabbbc"
Output: "2[2[abbb]c]"
仔细看还是有DP的影子, 字符串被compress到最短的时候, 子字符串(repeat pattern)也一定是由优化字符串构成. 当前问题由最优子问题构成, DP.
dp[i][j] 代表从i到j字符串的最优表达方式.
dp[i][j]的构成方式有三种
dp[i][j]在j-i<4的时候就是substring(i, j)
dp[i][j] 由 dp[i][k] 和 dp[k+1][j]两个字符串拼接而成
dp[i][j] 有 从i开始的重复字符串, 可以压缩得到. substr.length()/rptStr.length() + "[" + dp[i][k] + "]";
注意下标, 注意拼接的时候用dp[i][k],而不是 repeat String.
public class Solution {
public String encode(String s) {
String[][] dp = new String[s.length()][s.length()];
for(int l=0;l<s.length();l++) {
for(int i=0;i<s.length()-l;i++) {
int j = i+l;
String substr = s.substring(i,j+1);
dp[i][j] = substr;
if(j-i<4){
continue;
}
else{
for(int k =i;k<j;k++){
if(dp[i][k].length()+dp[k+1][j].length()<dp[i][j].length())
dp[i][j] = dp[i][k] + dp[k+1][j];
}
for(int k=i;k<=j;k++){
String rptStr = s.substring(i, k+1);
if(substr!=null && substr.length()%rptStr.length()==0 && substr.replaceAll(rptStr, "").length()==0){
String ss = substr.length()/rptStr.length() + "[" + dp[i][k] + "]";
if(ss.length() < dp[i][j].length()) {
dp[i][j] = ss;
}
}
}
}
}
}
return dp[0][s.length()-1];
}
}