给一个加密过的字符串解码，返回解码后的字符串。
加密方法是：k[c] ，表示中括号中的 c 字符串重复 k 次，例如 3[a] 解码结果是 aaa ，保证输入字符串符合规则。不会出现类似 3a , 3[3] 这样的输入。
数据范围：输出的字符串长度满足 
[编程题]字符串解码
import java.util.*;
/**
* NC199 字符串解码
* @author d3y1
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 类似 -> HJ50 四则运算
*
* @param s string字符串
* @return string字符串
*/
public String decodeString (String s) {
// return solution1(s);
// return solution11(s);
return solution111(s);
// return solution2(s);
}
/**
* 递归
* @param s
* @return
*/
private String solution1(String s){
int len = s.length();
StringBuilder result = new StringBuilder();
char ch;
int num = 0;
String part;
for(int i=0; i<len; i++){
ch = s.charAt(i);
// digit
if(Character.isDigit(ch)){
num = num*10+(ch-'0');
}
// [
else if(ch == '['){
int cnt = 1;
char next;
int j;
for(j=i+1; j<len; j++){
next = s.charAt(j);
if(next == '['){
cnt++;
}
if(next == ']'){
cnt--;
}
if(cnt == 0){
break;
}
}
part = decodeString(s.substring(i+1, j));
while(num > 0){
result.append(part);
num--;
}
i = j;
}
// letter
else if(Character.isLetter(ch)){
result.append(ch);
}
}
return result.toString();
}
/**
* 递归
* @param s
* @return
*/
private String solution11(String s){
int n = s.length();
StringBuilder result = new StringBuilder();
char ch;
int k = 0;
String c;
for(int i=0; i<n; i++){
ch = s.charAt(i);
// digit
if(Character.isDigit(ch)){
k = k*10+(ch-'0');
}
// [
else if(ch == '['){
int cnt = 1;
char next;
int j;
for(j=i+1; j<n; j++){
next = s.charAt(j);
if(next == '['){
cnt++;
}
if(next == ']'){
cnt--;
}
if(cnt == 0){
break;
}
}
c = decodeString(s.substring(i+1, j));
while(k > 0){
result.append(c);
k--;
}
i = j;
}
// letter
else if(Character.isLetter(ch)){
result.append(ch);
}
}
return result.toString();
}
/**
* 递归
* @param s
* @return
*/
private String solution111(String s){
int n = s.length();
StringBuilder sb = new StringBuilder();
int k;
char ch;
for(int i=0; i<n; i++){
k = 0;
ch = s.charAt(i);
// k[c]
if(Character.isDigit(ch)){
// k
while(Character.isDigit(ch)){
k = k*10+(ch-'0');
ch = s.charAt(++i);
}
// c
String c = "";
if(ch == '['){
int cnt = 1;
int j = i+1;
while(j < n){
if(s.charAt(j) == '['){
cnt++;
}
if(s.charAt(j) == ']'){
cnt--;
}
if(cnt == 0){
c = decodeString(s.substring(i+1, j));
break;
}
j++;
}
i = j;
}
// c重复k次
while(k-- > 0){
sb.append(c);
}
}
// c
else if(Character.isLetter(ch)){
sb.append(ch);
}
}
return sb.toString();
}
/**
* 迭代: 栈
* @param s
* @return
*/
private String solution2(String s){
Stack<Integer> numStack = new Stack<>();
Stack<String> resStack = new Stack<>();
StringBuilder result = new StringBuilder();
int len = s.length();
char ch;
int num = 0;
for(int i=0; i<len; i++){
ch = s.charAt(i);
// digit
if(Character.isDigit(ch)){
num = num*10 + (ch-'0');
}
// [
else if(ch == '['){
numStack.push(num);
num = 0;
resStack.push(result.toString());
result = new StringBuilder();
}
// letter
else if(Character.isLetter(ch)){
result.append(ch);
}
// ]
else if(ch == ']'){
int times = numStack.pop();
StringBuilder part = new StringBuilder(resStack.pop());
for(int j=1; j<=times; j++){
part.append(result);
}
result = part;
}
}
return result.toString();
}
}
发表于 2025-01-31 14:13:30
回复(0)
public String decodeString (String s) {
if (s == null || s.length() == 0) {
return "";
}
StringBuilder result = new StringBuilder();
StringBuilder numStr = new StringBuilder();
LinkedList<Integer> numStack = new LinkedList<>();
LinkedList<StringBuilder> resultStack = new LinkedList<>();
for (char ch : s.toCharArray()) {
if (Character.isDigit(ch)) {
numStr.append(ch);
} else if (ch == '[') {
numStack.push(Integer.valueOf(numStr.toString()));
resultStack.push(result);
result = new StringBuilder();
numStr = new StringBuilder();
} else if (ch == ']') {
StringBuilder temp = resultStack.pop();
int num = numStack.pop();
for (int i = 0; i < num; i++) {
temp.append(result);
}
result = temp;
} else {
result.append(ch);
}
}
return result.toString();
}
发表于 2024-05-01 23:27:17
回复(0)
import java.util.*;
public class Solution {
public String decodeString (String s) {
// write code here
if (s == null || s.length() == 0) return "";
return process(s.toCharArray(), 0, s.length() - 1);
}
private String process(char[] arr, int start, int end ) {
if(start > arr.length - 1 || end > arr.length - 1) return "";
StringBuilder ans = new StringBuilder();
for (int i = start; i <= end; i ++) {
if (Character.isDigit(arr[i])) {
// k[ ? ]
int idR = findTrueRight(i + 2, arr);
String ret = process(arr, i + 2, idR - 1);
//StringBuilder sb = new StringBuilder();
int k = Integer.parseInt(arr[i] + "");
for (int w = 0; w < k; w ++) {
ans.append(ret);
}
i = idR;
} else {
ans.append(arr[i]);
}
}
return ans.toString();
}
private int findTrueRight(int idx, char[] arr) {
int countLeft = 1;
while (true) {
if (arr[idx] == '[') {
countLeft ++;
} else if (arr[idx] == ']') {
countLeft --;
}
if (countLeft == 0) {
break;
}
idx ++;
}
return idx;
}
}
发表于 2024-02-06 15:54:51
回复(0)
这道面试题我的水平也就这样了
public String decodeString (String s) {
StringBuilder ss = new StringBuilder();
StringBuilder sx = new StringBuilder();
Stack<Character> st = new Stack<>();
String sf="";
String se="";
int c=0;
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='['){
st.push('[');
}else if(Character.isDigit(s.charAt(i))){
st.push(s.charAt(i));
//c*=Integer.parseInt(String.valueOf(s.charAt(i)));
}else if(Character.isLetter(s.charAt(i))){
st.push(s.charAt(i));
}else if(s.charAt(i)==']'){
ss.delete(0,ss.length());
sf="";
while(st.peek()!='['){
sf+=String.valueOf(st.pop());
}
st.pop();
c=Integer.parseInt(String.valueOf(st.pop()));
int j=0;
while(j<c){
ss.append(sf);
j++;
}
ss.reverse();
for(char ch:ss.toString().toCharArray()){
st.push(ch);
}
}
}
while(!st.isEmpty()){
sx.insert(0,st.pop());
}
return sx.toString();
}
发表于 2022-06-18 17:56:50
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
