R**y
发帖数: 72 | 1 题目如下，要求recursive 和 non recursive解法
write a program that given a 7 digit telephone number, could print all
possible combinations of letters that each number could represent.
second part: if the telephone number changes to 12 digits one
recursive 解法很清晰，建立一个字典，然后递归就好了。
iterative 解法，我就卡住了，google了一下，有一个解法如下:
private static ArrayList processOneNumber(ArrayList input, int[] phoneNum,
int currentNum) {
ArrayList output = new ArrayList();
int numberToProcess = phoneNum[currentNum];
char c;
// process 1st number
if (input.isEmpty()) {
if (TelephoneWords.isOneOrZero(numberToProcess)) {
c = TelephoneWords.getCharKey(numberToProcess, 0);
output.add(Character.toString(c));
} else {
for (int i = 0; i < 3; i++) {
c = TelephoneWords.getCharKey(numberToProcess, i);
output.add(Character.toString(c));
}
}
} else { // process rest of the number
for (String result : input) {
if (TelephoneWords.isOneOrZero(numberToProcess)) {
c = TelephoneWords.getCharKey(numberToProcess, 0);
output.add(result.concat(Character.toString(c)));
} else {
for (int i = 0; i < 3; i++) {
c = TelephoneWords.getCharKey(numberToProcess, i);
output.add(result.concat(Character.toString(c)));
}
}
}
return output;
}
这个解法每次处理一个digit然后存储当前结果，下一次调用将新的char 附加到后面。
这样的解法下来，arraylist 巨大无比，而且有很多中间的结果，比如A，B,C 这样的
不是最终结果的过渡字符。
原书的解法貌似错了,希望各位大神多多指教 | j*****y
发帖数: 1071 | 2 搞个 for循环就可以了吧
【在 R**y 的大作中提到】
: 题目如下，要求recursive 和 non recursive解法
: write a program that given a 7 digit telephone number, could print all
: possible combinations of letters that each number could represent.
: second part: if the telephone number changes to 12 digits one
: recursive 解法很清晰，建立一个字典，然后递归就好了。
: iterative 解法，我就卡住了，google了一下，有一个解法如下:
: private static ArrayList processOneNumber(ArrayList input, int[] phoneNum,
: int currentNum) {
: ArrayList output = new ArrayList();
: int numberToProcess = phoneNum[currentNum];
| c*****a
发帖数: 808 | 3 import java.util.Hashtable;
public class Solution {
Hashtable Dict = new Hashtable ()
;
public ArrayList letterCombinations(String digits) {
ArrayList res = new ArrayList();
if(digits.length()==0){
res.add("");
return res;
}
Dict.put(2, new String[]{"a", "b", "c"});
Dict.put(3, new String[]{"d", "e", "f"});
Dict.put(4, new String[]{"g", "h", "i"});
Dict.put(5, new String[]{"j", "k", "l"});
Dict.put(6, new String[]{"m", "n", "o"});
Dict.put(7, new String[]{"p", "q", "r", "s"});
Dict.put(8, new String[]{"t", "u", "v"});
Dict.put(9, new String[]{"w", "x", "y", "z"});
permute(res,digits, "", digits.length());
return res;
}
public void permute(ArrayList res, String digits, String buffer,
int size){
if(buffer.length()==size){
res.add(buffer);
return;
}
for(int i =0; i
for(String c: Dict.get(digits.charAt(i)-48))
permute(res, digits.substring(i+1), buffer + c,size);
}
}
}
刚刚写的，跟subset of string差不多,写法一样,就加了一个for loop..
//subset of string eg, ab: a, b , ab
public static void subset(String s){
if(s.length()==0) return;
subset(s, "");
}
public static void subset(String s,String res){
System.out.println(res);
for(int i =0;i
subset(s.substring(i+1), res+s.charAt(i));
} | R**y
发帖数: 72 | 4 一个for循环够么？ 一个数字对应三个letter，然后最少有7个数字，这里就是两重循
环了。
【在 j*****y 的大作中提到】
: 搞个 for循环就可以了吧
| R**y
发帖数: 72 | 5 这个解法是recursion吧。
()
【在 c*****a 的大作中提到】
: import java.util.Hashtable;
: public class Solution {
: Hashtable Dict = new Hashtable ()
: ;
: public ArrayList letterCombinations(String digits) {
: ArrayList res = new ArrayList();
: if(digits.length()==0){
: res.add("");
: return res;
: }
| j*****y
发帖数: 1071 | 6 之前要搞一个 vectorv 记录每个 key对应的字母
for(int i = 0; i < digits.length(); ++i)
{
for(int j = 0; j < v[digits[i] - '1'].length(); ++j)
{
}
}
我这里假设数字 1 和 0 不会用到，因为 key board里面没有对应这两个数字的字母
【在 R**y 的大作中提到】
: 一个for循环够么？ 一个数字对应三个letter，然后最少有7个数字，这里就是两重循
: 环了。
|
|
