所以我使用动态编程解决了leetcode的这个问题--> https://leetcode.com/problems/decode-ways/
但是在解决下图中给出的类似问题时遇到了麻烦。我们需要实际打印所有字符串解码而不是计算它们,我在下面附上了一个代码,但它不适用于任何长度超过 2 的字符串。我做错了什么??
package MiscStringQs;
import java.util.ArrayList;
import java.util.Scanner;
public class printDecodeWays {
static String str;
static Scanner sc=new Scanner(System.in);
public static void main(String[] args) {
input();
System.out.println(decodeString());
}
public static void input() {
str = sc.next();
}
public static ArrayList<String> decodeString() {
if(str.charAt(0)=='0') {
ArrayList<String> ans = new ArrayList<>(); ans.add("");
return ans;
}
if(str.length()==1) {
ArrayList<String> ans = new ArrayList<>(); ans.add(Character.toString(str.charAt(0)+48));
return ans;
}
int N = str.length();
char scan;
ArrayList <String> ans1 = new ArrayList<>(); //ans1.add("");
ArrayList <String> ans2 = new ArrayList<>(); //ans2.add("");
ArrayList <String> prevAns = new ArrayList<>(); prevAns.add("");
String fetch = Character.toString(str.charAt(0)+48); //convert number to alphabet mapping
ans1.add(fetch);
String tempStr;
char prev=str.charAt(0);
for(int i=2;i<=N;i++) {
int strIndex = i-1;
scan = str.charAt(strIndex);
if(scan != '0') {
for(int j=0;j<ans1.size();j++) {
tempStr = ans1.get(j) + Character.toString(scan+48);
ans2.add(j, tempStr);
if(ans1.size()>4) {
System.exit(0);
}
}
}
if( checkNo(prev,scan) <=26 ) {
for(int j=0;j<prevAns.size();j++) {
String comboStr = Character.toString(prev)+ Character.toString(scan);
int comboInt = Integer.parseInt(comboStr);
char comboChar = (char) (comboInt + 96);
tempStr = prevAns.get(j) + Character.toString(comboChar);
ans2.add(tempStr);
}
}
prevAns = (ArrayList<String>) ans1.clone();
ans1= (ArrayList<String>) ans2.clone();
prev = scan;
}
return ans2;
}
public static int checkNo(char prev,char scan) {
return 10* (prev-'0') + (scan-'0');
}
}
对于您的示例“1125”,您首先取最后一个数字 5,得到字符“e”,现在您的字符串是“e”,用手中的字符串递归剩余的数字“112”。类似地取最后两个数字 25,得到字符 'y',现在你的字符串是“y”,手中的字符串在剩余的数字“11”上递归。
递归时要注意 j = 10。
代码将是:
import java.util.*;
public class Main
{
public static void main(String[] args) {
List<String> list = new ArrayList<>();
getAllStrings(list, 1125, "");
System.out.println(list);
list = new ArrayList<>();
getAllStrings(list, 10101, "");
System.out.println(list);
}
private static void getAllStrings(List<String> list, int n, String s) {
if ( n == 0 ) {
return;
} else if ( n < 11 ) {
list.add(String.valueOf((char)(96+n)) + s);
} else if ( n < 27 ) {
list.add(String.valueOf((char)(96+n)) + s);
if ( n % 10 != 0 ) {
getAllStrings(list, n/10, String.valueOf((char)(96+n%10)) + s);
}
} else {
if ( n % 10 != 0 ) {
getAllStrings(list, n/10, String.valueOf((char)(96+n%10)) + s);
}
if (( n - n % 10) % 100 != 0 ) {
getAllStrings(list, n/100, String.valueOf((char)(96+n%100)) + s);
}
}
}
}
输出:
[kbe, aabe, ale, ky, aay]
[jja]
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句