問題概要
与えられた文字列には、括弧で囲まれたパターンと繰り返し回数が含まれています。この文字列を解釈し、括弧内のパターンを繰り返して最終的な文字列を返すことが目標です。括弧は入れ子になっている場合があり、それぞれのパターンは括弧の外にある数字に基づいて複数回繰り返されます。
例
- 入力:
"3(a2(b))ef"
出力:"abbabbabbef" - 入力:
"2(2(ab)3(2(ac)))"
出力:"abacabacabacabacabacabacabacabac"
使用するデータ構造
1. スタック (Stack)
- スタックはLIFO（Last In, First Out）構造で、最後に追加された要素が最初に取り出されます。
- この問題では、括弧を効果的に処理するためにスタックを使用します。入れ子になった括弧に遭遇したとき、スタックを利用してその括弧内のパターンを抽出し、繰り返し処理を行います。
問題解決のアプローチ
1. 文字列の走査と文字の処理
- 入力文字列を1文字ずつ走査し、各文字をスタックに格納します。
- もし
)に遭遇した場合、スタックを用いて直前の括弧内のパターンを処理します。
2. 括弧内のパターン抽出
-
)を見つけたとき、(が出てくるまでスタックから文字を取り出してパターンを構成します。 - パターンは逆順で格納されているため、正しい順序に並び替えます。
3. 繰り返し回数の計算
- 括弧の外側にある数字を探し、繰り返し回数を計算します。複数桁の数字も処理できるように
idxを使用して桁数を乗算しながら計算します。 - 繰り返し回数が0の場合、そのパターンをそのままスタックに格納し、0でない場合はパターンを繰り返して再びスタックに格納します。
4. 最終文字列の生成
- 全ての文字を処理した後、スタックに残った文字を順に取り出し、最終的な文字列を構成します。
- 最終文字列は逆順で格納されているため、再度逆にして返します。
重要なポイント
-
スタックを使った効率的な括弧処理:
- 入れ子になった括弧のパターンを効率的に管理できます。
-
繰り返し回数の処理:
- 文字列パターンを正確に拡張するために繰り返し回数を計算します。
-
入れ子になった括弧の解決:
- スタックを使用すれば、入れ子の構造でも正確にパースできます。
コード例
public class Solution {
public String solution(String s) {
StringBuilder answer = new StringBuilder();
Stack<String> stack = new Stack<>();
for (char item : s.toCharArray()) {
if (item == ')') {
StringBuilder tmp = new StringBuilder();
while (!stack.isEmpty() && !stack.peek().equals("(")) {
tmp.append(stack.pop());
}
tmp.reverse();
if (stack.peek().equals("(")) {
stack.pop();
}
int idx = 1;
int sum = 0;
while (!stack.isEmpty() && Character.isDigit(stack.peek().charAt(0))) {
sum += Integer.parseInt(stack.pop()) * idx;
idx *= 10;
}
if (sum == 0) {
stack.push(tmp.reverse().toString());
} else {
StringBuilder tmp2 = new StringBuilder();
for (int i = 0; i < sum; i++) {
tmp2.append(tmp.toString());
}
stack.push(tmp2.reverse().toString());
}
} else {
stack.push(item + "");
}
}
while (!stack.isEmpty()) {
answer.append(stack.pop());
}
return answer.reverse().toString();
}
}
結論
スタックを使用することで、入れ子になった括弧や繰り返し構造を効率的に処理することができます。このアルゴリズムは、文字列を順に走査し、パターンを展開して繰り返し処理を行い、最終的な文字列を構成する方法で設計されています。