最后更新
三刷
13-Jan-2017
貌似像DFS。
String做法里有一种思想，每个char都可以选择考虑或者不考虑。
这里考虑就是缩减为数字; 不考虑就是把前面有的数字先加了，再以当前为缩减起始位置。。
所以你得有2个pointer一个记录缩减的数量，另一个记录指针在字符串中的位置。
public class Solution {
public List<String> generateAbbreviations(String word) {
List<String> res = new ArrayList<>();
if (word.length() == 0) return res;
dfs(res, word, 0, 0, new StringBuilder());
return res;
}
public void dfs(List<String> res, String s, int index, int len, StringBuilder sb) {
int tempLen = sb.length();
if (index == s.length()) {
if (len != 0) sb.append(len);
res.add(sb.toString());
} else {
dfs(res, s, index+1, len+1, sb);
if (len != 0) sb.append(len);
dfs(res, s, index+1, 0, sb.append(s.charAt(index)));
}
sb.setLength(tempLen);
}
}
09-Nov-2016
首先想到的是遍历，对于每个单词的字母都遍历，比如
spy: 1py,s1y,sp1
然后每个遍历完的单词再遍历。。左右有数字就合并比如
1py: 11py=>2py, 1p1
这样。。
但是单词长了会出现重复，于是又加了一个SET判断重复，毕竟不是在构造前就判断重复，所以估计会TLE。
结果居然AC了。
public class Solution {
public List<String> generateAbbreviations(String word)
{
List<String> res = new ArrayList<String>();
Set<String> set = new HashSet<String>();
if(word.length() == 0)
{
res.add("");
return res;
}
if(word.length() == 1)
{
res.add(word);
res.add("1");
return res;
}
tonightTheMusicSeemsSoLoud(res,word,set);
return res;
}
public void tonightTheMusicSeemsSoLoud(List<String> res, String word, Set<String> set)
{
if(set.contains(word)) return;
res.add(word);
set.add(word);
for(int i = 0; i < word.length();i++)
{
if(word.charAt(i) < '0' || word.charAt(i) > '9')
{
String tempWord = maybeItsBetterThisWay(i,word);
tonightTheMusicSeemsSoLoud(res,new String(tempWord),set);
}
}
}
// replace letter with number
public String maybeItsBetterThisWay(int m, String word)
{
//System.out.println(m + " " + word);
int l = m - 1;
int r = m + 1;
int lNum = 0;
int rNum = 0;
int pow = 1;
while(l >= 0 && word.charAt(l) >= '0' && word.charAt(l) <= '9')
{
lNum = (word.charAt(l)-'0')*pow + lNum;
pow*=10;
l--;
}
while(r < word.length() && word.charAt(r) >= '0' && word.charAt(r) <= '9')
{
rNum = rNum*10 + word.charAt(r) - '0';
r++;
}
int val = lNum + rNum + 1;
String res = "";
if(l < 0 && r >= word.length()) res = Integer.toString(val);
else if(l < 0) res = Integer.toString(val) + word.substring(r);
else if(r >= word.length()) res = word.substring(0,l+1) + Integer.toString(val);
else res = word.substring(0,l+1) + Integer.toString(val) + word.substring(r);
//System.out.println(res);
return res;
}
}
耗时220ms。。据统计，该数据被98%的人羞辱。。。
感觉问题出在重复上，比如
s2 2p 1p1
这3个单词下一步的结果都是3。。
如果单词很长重复的情况会更多。
。。经过一番思考。。
在纸上写了一下 发现了一个规律
比如在改变fey的时候顺序是这样的
fey - 1ey - 2y - 3
fey - f1y - f2
fey - fe1
一开始的思路是所有单词都尝试把每一个letter换成1，然后和左右合并成digit。
现在不用尝试每一个letter，只从第一个数字开始，比如：
本来f1y是按顺序从头尝试替换f和y，现在从里面的1开始，只需要替换y就行了，就避免了重复。同理，fe1不按顺序替换f，e，从第一个数字1开始替换，发现1后面没了，直接停止就行了。。避免了重复。。
在原来基础上修改一下，去掉检查重复的SET，加1个变量记录开始位置。
public class Solution {
public List<String> generateAbbreviations(String word)
{
List<String> res = new ArrayList<String>();
//Set<String> set = new HashSet<String>();
if(word.length() == 0)
{
res.add("");
return res;
}
if(word.length() == 1)
{
res.add(word);
res.add("1");
return res;
}
tonightTheMusicSeemsSoLoud(res,word,0);
return res;
}
public void tonightTheMusicSeemsSoLoud(List<String> res, String word,int m)
{
res.add(word);
for(int i = m; i < word.length();i++)
{
if(word.charAt(i) < '0' || word.charAt(i) > '9')
{
String tempWord = maybeItsBetterThisWay(i,word);
tonightTheMusicSeemsSoLoud(res,new String(tempWord),i);
}
}
}
// replace letter with number
public String maybeItsBetterThisWay(int m, String word)
{
//System.out.println(m + " " + word);
int l = m - 1;
int r = m + 1;
int lNum = 0;
int rNum = 0;
int pow = 1;
while(l >= 0 && word.charAt(l) >= '0' && word.charAt(l) <= '9')
{
lNum = (word.charAt(l)-'0')*pow + lNum;
pow*=10;
l--;
}
while(r < word.length() && word.charAt(r) >= '0' && word.charAt(r) <= '9')
{
rNum = rNum*10 + word.charAt(r) - '0';
r++;
}
int val = lNum + rNum + 1;
String res = "";
if(l < 0 && r >= word.length()) res = Integer.toString(val);
else if(l < 0) res = Integer.toString(val) + word.substring(r);
else if(r >= word.length()) res = word.substring(0,l+1) + Integer.toString(val);
else res = word.substring(0,l+1) + Integer.toString(val) + word.substring(r);
//System.out.println(res);
return res;
}
}
25ms..只战胜了33%。。。
似乎想不出什么好办法。。先这样了，看看别人怎么做的。
二刷。
这个题抄袭了别人的做法。
（https://discuss.leetcode.com/topic/32765/java-14ms-beats-100）
主要是剥离出一个模型比较困难。
每到一个位置都可以选择是否转化为数字。
准地说是选择马上转化还是晚点转化：
晚点转化的话需要记住有个字母要转化，积累的个数。
马上转化就把积累的个数一起转化了（或者根本就没有要转化的，积累个数是0的时候），然后积累个数清0.
有点绕的。
T(n) = 2T(n-1) + 2T(n-2)...2T(1) + 乱七八糟的常熟运算
T(n-1) = 2T(n-2)...2T(1)
T(n) = 6T(n-1)
Time Complexity: O(6^n) 是这样么。。
Space Complexity: O(6^n)
public class Solution {
public List<String> generateAbbreviations(String word) {
List<String> res = new ArrayList<>();
dfs(res, word.toCharArray(), new StringBuilder(), 0, 0);
return res;
}
public void dfs(List<String> res, char[] word, StringBuilder s, int pos, int num) {
int len = s.length();
if (word.length == pos) {
if (num != 0) s.append(num);
res.add(s.toString());
} else {
// not change
dfs(res, word, s, pos+1, num+1);
if (num != 0) {
s.append(num);
}
s.append(word[pos]);
dfs(res, word, s, pos+1, 0);
}
s.setLength(len);
}
}