leetcode-394-文字列復号-java
6997 ワード
テーマとテスト
解法1(成功、3 ms、遅い)
char要素を装うstackを確立し、文字列sを遍歴し、「以外の要素に出会ったらstackに参加し、出会った」と論理を開始する.
まず[]間の文字列baseを見つけ、[]の前の数字realNumを見つけ、1つの文字列baseのrealNum次=resultを生成し、最後にresultをstackに追加します.
遍歴が終わったら、stackには文字が入っていて、resultを順番に入れた後、反転すればいいです.
解法2(他人の)
この問題では、2[a 2[bc]]のようなカッコネストが発生する可能性があります.この場合、abcbcabcbcに変換するには、まず2[abcbc]に変換することができます.アルファベット、数字、カッコを独立したTOKENと見なし、スタックでこれらのTOKENを維持することができます.具体的には、このスタックを巡ります.
現在の文字が桁である場合、1つの数字(連続する複数の桁)が解析され、スタックに格納されます.
現在の文字がアルファベットまたは左かっこの場合は、直接スタックに入ります.
現在の文字が右かっこの場合、スタックを出て、左かっこまでスタックを出て、スタックのシーケンスを反転して文字列につなぎ、スタックの一番上の数字を取り出します(スタックの一番上は必ず数字ですが、なぜか考えてみてください).この文字列が現れるべき回数であり,この回数と文字列に基づいて新しい文字列を構築しスタックに入れる.
上記の操作を繰り返し、最終的にスタック内の要素をスタックの底からスタックの頂上までの順序でつなぎ合わせると、答えが得られます.注意:ここでは、スタック操作を不定長配列でシミュレートすることができ、スタックの底からスタックの頂上への遍歴を容易にすることができます.
解法3(他人の)
この問題を再帰的に解決し、文字列を左から右に解析することもできます.
現在の位置が数値ビットである場合、後ろには必ず角カッコで表される文字列が含まれます.つまり、k[...]:
我々はまず1つの数字を解析して、それから左括弧に解析して、再帰的に下に後ろの内容を解析して、対応する右括弧に出会って帰って、この時私達は解析した数字xによって解析した括弧の中の文字列s’に基づいて1つの新しい文字列xを構築することができます× s′;
我々はk[...]解析が終了したら、再帰関数を再度呼び出し、右かっこ右の内容を解析します.
現在の位置がアルファベットビットである場合、現在のアルファベットを直接解析し、このアルファベットの後ろの内容を再帰的に下に解析します.
ここで言うのが抽象的だと思ったら、コードと結びつけてこの過程を理解することができます.
package pid394;
/*394.
， 。
: k[encoded_string]， encoded_string k 。 k 。
； ， 。
， ， k ， 3a 2[4] 。
1：
：s = "3[a]2[bc]"
："aaabcbc"
2：
：s = "3[a2[c]]"
："accaccacc"
3：
：s = "2[abc]3[cd]ef"
："abcabccdcdcdef"
4：
：s = "abc3[cd]xyz"
："abccdcdcdxyz"
*/
public class main {
public static void main(String[] args) {
String [] testTable = {"3[a]2[bc]","3[a2[c]]","2[abc]3[cd]ef"};
for (String ito : testTable) {
test(ito);
}
}
private static void test(String ito) {
Solution solution = new Solution();
String rtn;
long begin = System.currentTimeMillis();
System.out.print(ito);
System.out.println();
//
rtn= solution.decodeString(ito);//
long end = System.currentTimeMillis();
System.out.println("rtn=" );
System.out.print(rtn);
System.out.println();
System.out.println(" ：" + (end - begin) + "ms");
System.out.println("-------------------");
}
}
解法1(成功、3 ms、遅い)
char要素を装うstackを確立し、文字列sを遍歴し、「以外の要素に出会ったらstackに参加し、出会った」と論理を開始する.
まず[]間の文字列baseを見つけ、[]の前の数字realNumを見つけ、1つの文字列baseのrealNum次=resultを生成し、最後にresultをstackに追加します.
遍歴が終わったら、stackには文字が入っていて、resultを順番に入れた後、反転すればいいです.
package pid394;
import java.util.Stack;
class Solution {
public String decodeString(String s) {
int length = s.length();
if(length == 0){
return "";
}
Stack stack = new Stack<>();
for(int i = 0;i < length;i++){
char now = s.charAt(i);
if(now != ']'){
stack.push(now);
}else{
// pop [， []
StringBuilder base = new StringBuilder();
while(true){
char c = stack.pop();
if(c == '['){
break;
}else{
base.append(c);
}
}
// ，
base = base.reverse();
// []
StringBuilder num = new StringBuilder();
while(!stack.isEmpty()){
char c = stack.pop();
if(c < '0' || c > '9'){
stack.push(c);
break;
}else{
num.append(c);
}
}
num = num.reverse();
int realNum = Integer.valueOf(num.toString());
// base*realNum
StringBuilder result = new StringBuilder();
for(int j=0;j 解法2(他人の)
この問題では、2[a 2[bc]]のようなカッコネストが発生する可能性があります.この場合、abcbcabcbcに変換するには、まず2[abcbc]に変換することができます.アルファベット、数字、カッコを独立したTOKENと見なし、スタックでこれらのTOKENを維持することができます.具体的には、このスタックを巡ります.
現在の文字が桁である場合、1つの数字(連続する複数の桁)が解析され、スタックに格納されます.
現在の文字がアルファベットまたは左かっこの場合は、直接スタックに入ります.
現在の文字が右かっこの場合、スタックを出て、左かっこまでスタックを出て、スタックのシーケンスを反転して文字列につなぎ、スタックの一番上の数字を取り出します(スタックの一番上は必ず数字ですが、なぜか考えてみてください).この文字列が現れるべき回数であり,この回数と文字列に基づいて新しい文字列を構築しスタックに入れる.
上記の操作を繰り返し、最終的にスタック内の要素をスタックの底からスタックの頂上までの順序でつなぎ合わせると、答えが得られます.注意:ここでは、スタック操作を不定長配列でシミュレートすることができ、スタックの底からスタックの頂上への遍歴を容易にすることができます.
class Solution {
int ptr;
public String decodeString(String s) {
LinkedList stk = new LinkedList();
ptr = 0;
while (ptr < s.length()) {
char cur = s.charAt(ptr);
if (Character.isDigit(cur)) {
//
String digits = getDigits(s);
stk.addLast(digits);
} else if (Character.isLetter(cur) || cur == '[') {
//
stk.addLast(String.valueOf(s.charAt(ptr++)));
} else {
++ptr;
LinkedList sub = new LinkedList();
while (!"[".equals(stk.peekLast())) {
sub.addLast(stk.removeLast());
}
Collections.reverse(sub);
//
stk.removeLast();
// sub
int repTime = Integer.parseInt(stk.removeLast());
StringBuffer t = new StringBuffer();
String o = getString(sub);
//
while (repTime-- > 0) {
t.append(o);
}
//
stk.addLast(t.toString());
}
}
return getString(stk);
}
public String getDigits(String s) {
StringBuffer ret = new StringBuffer();
while (Character.isDigit(s.charAt(ptr))) {
ret.append(s.charAt(ptr++));
}
return ret.toString();
}
public String getString(LinkedList v) {
StringBuffer ret = new StringBuffer();
for (String s : v) {
ret.append(s);
}
return ret.toString();
}
}
解法3(他人の)
この問題を再帰的に解決し、文字列を左から右に解析することもできます.
現在の位置が数値ビットである場合、後ろには必ず角カッコで表される文字列が含まれます.つまり、k[...]:
我々はまず1つの数字を解析して、それから左括弧に解析して、再帰的に下に後ろの内容を解析して、対応する右括弧に出会って帰って、この時私達は解析した数字xによって解析した括弧の中の文字列s’に基づいて1つの新しい文字列xを構築することができます× s′;
我々はk[...]解析が終了したら、再帰関数を再度呼び出し、右かっこ右の内容を解析します.
現在の位置がアルファベットビットである場合、現在のアルファベットを直接解析し、このアルファベットの後ろの内容を再帰的に下に解析します.
ここで言うのが抽象的だと思ったら、コードと結びつけてこの過程を理解することができます.
class Solution {
String src;
int ptr;
public String decodeString(String s) {
src = s;
ptr = 0;
return getString();
}
public String getString() {
if (ptr == src.length() || src.charAt(ptr) == ']') {
// String -> EPS
return "";
}
char cur = src.charAt(ptr);
int repTime = 1;
String ret = "";
if (Character.isDigit(cur)) {
// String -> Digits [ String ] String
// Digits
repTime = getDigits();
//
++ptr;
// String
String str = getString();
//
++ptr;
//
while (repTime-- > 0) {
ret += str;
}
} else if (Character.isLetter(cur)) {
// String -> Char String
// Char
ret = String.valueOf(src.charAt(ptr++));
}
return ret + getString();
}
public int getDigits() {
int ret = 0;
while (ptr < src.length() && Character.isDigit(src.charAt(ptr))) {
ret = ret * 10 + src.charAt(ptr++) - '0';
}
return ret;
}
}