原题链接
思路
对于字符串k[encoding]
对于这样的形式,我们要加encoding
重复k次;
从左向右扫描字符串
- 如果说遇见字符,就直接将该字符添加到结果中
- 如果说 遇见
k[encoding]
的形式,我们首先要做的是就是将k和encoding
解析出来。然后将 encoding
重复k次,添加到结果中
可以使用DFS来做,每次遇见一个规则,就向下递归一层,求得结果,就回溯一层
代码
class Solution {
private int u = 0;
public String dfs(String s)
{
StringBuffer res = new StringBuffer();
while(u < s.length() && s.charAt(u) != ']')
{
if(s.charAt(u) >= 'a' && s.charAt(u) <= 'z' || s.charAt(u) >= 'A' && s.charAt(u) <= 'Z')
{
res.append(s.charAt(u));
u++;
} else if(s.charAt(u) >= '0' && s.charAt(u) <= '9') {
int k = u;
while(s.charAt(k) >= '0' && s.charAt(k) <= '9') k++;
int time = Integer.valueOf(s.substring(u,k));
u = k + 1;
String y = dfs(s);
u++;
y = y.repeat(time);
res.append(y);
}
}
return res.toString();
}
public String decodeString(String s) {
return dfs(s);
}
}