Java recursion phone number letters_问答_开发者

How do you write a java program using a recursive method that takes in an int like "234" and converts this into the corresponding letters on a phone pad (2 = ABC, 3 = DEF, etc), and prints o开发者_开发技巧ut the permutations of this? e.g.:

input = 234

output = ADG ADH ADI AEG AEH AEI AFG AFH AFI BDG BDH BDI BEG BEH BEI BFG BFH BFI CDG CDH CDI CEG CEH CEI CFG CFH CFI

input = 89

output = TW TX TY TZ UW UX UY UZ VW VX VY VZ

Generating permutations alone would constitute a good homework assignment, let alone the forced recursion and phone number distraction.

Small numbers of permutations can be generated efficiently through a method analogous to sorting networks. A sequence of n elements has n! permutations (assuming a full draw, with each permutation consisting of n elements as well). Observe that for a two-element sequence, there are two permutations:

the original sequence, and
the two elements swapped.

For a three-element sequence, there are six permutations:

the permutations of the bottom two elements, then
rotate the sequence one cell right (or left), and
the permutations of the bottom two elements, then
rotate the sequence one cell left (or right, opposite of above), and
the permutations of the bottom two elements.

That is, it's the two-element version performed three times, with two intervening transformations. Now, a four-element sequence has twenty-four permutations:

the permutations of the bottom three elements, then
save position 1, assign 0 to 1, 3 to 0, and the saved value to 3, and
the permutations of the bottom three elements, then
swap positions 0 and 2, swap positions 1 and 3 (or rotate right by 2), and
the permutations of the bottom three elements, then
save position 3, assign 2 to 3, 0 to 2, and the saved value to 0, and
the permutations of the bottom three elements.

Are you starting to see a pattern? Notice the recursive nature of the solution?

Above four elements, the patterns are harder to spot. You can iterate down the sequence, swapping the chosen element with the last element, reversing the sequence, expanding the bottom 24 permutations each time.

Try writing it out on paper, recording the steps you take to shuffle the elements, and you'll find you've written the program you need.

Note too that most of the solutions posted here use type String and keep chopping it up and reassembling it. String is a poor choice, given that it's immutable, when generating permutations is best done by swapping and rotating elements in a vector (really, a ring).

It's the rare case that you actually have to write the letters out to the destination stream, so bias your solution against that operation. Use an array of characters and write the characters to the stream one-by-one when it's time to emit a particular permutation. Forming a string just to dump the entry to a stream involves unnecessary allocation and copying.

Take input, convert to string
Call function generate(String prefix, String suffix) with empty prefix and converted input as suffix
Inside generate(), remove the first digit from suffix, map it to an array of corresponding letters and recursively call generate() for each letter from the array, appending it to the prefix.

import java.util.ArrayList;

class PhoneNumbers
{
    public static void main(String[] args)
    {
        for (String result: convert(args[0]))
            System.out.println(result);
    }

    public static ArrayList<String> convert(String phoneNumber)
    {           
        int digit = Integer.parseInt(phoneNumber.substring(0, 1));
        String letters = new String[] {
            "0",
            "1",
            "ABC",
            "DEF",
            "GHI",
            "JKL",
            // etc...
        }[digit];

        ArrayList<String> result = new ArrayList<String>();

        for (int i = 0; i < letters.length(); ++i) {
            char letter = letters.charAt(i);
            if (phoneNumber.length() > 1) {
                for (String rest: convert(phoneNumber.substring(1)))
                    result.add(letter + rest);
            } else {
                result.add("" + letter);
            }
        }

        return result;
    }
}

java PhoneNumbers 234

ADG
ADH
ADI
AEG
AEH
AEI
AFG
AFH
AFI
...

Here's a version without either array or arraylist. Results are printed to stdout as you requested.

String[] allLetters = new String[] {
                "0",
                "1",
                "ABC",
                "DEF",
                "GHI",
                "JKL",
                // etc...
        };

public static void convert(String phoneNumber)
{
  convertSubstring(phoneNumber,"");
}

private static void convertSubstring(String phoneNumber, String convertedLetters)
{                   
  int digit = Integer.parseInt(phoneNumber.substring(0, 1));
  String letters=allLetters[digit];
  String remainingString=phoneNumber.substring(1);

  for (int i = 0; i < letters.length(); ++i) 
  {
     char letter = letters.charAt(i);
     String result=convertedLetters+letter;
     if (remainingString.length()==0)
        System.out.println(result);
     else
        convertSubstring(remainingString, result);
  }
}

public class printKeypad {
public static char[] keynotes(int n)
{
    String s[]= {"","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    String s1=s[n-1];
    char c[]=new char[s1.length()];
    for(int i=0;i<c.length;i++)
    {
        c[i]=s1.charAt(i);
    }
    return c;
}
public static void printKeypad(int n)
{
    printKeypad(n,"");
}
public static void printKeypad(int n,String output)
{
    if(n==0)
    {
        System.out.println(output);
        return;
    }
    char c[]=keynotes(n%10);
    for(int i=0;i<c.length;i++)
    {
        printKeypad(n/10,output+c[i]);
    }
}
public static void main(String[] args) {
    int n=23;
    printKeypad(n);
}

} //both the printing as well as the returning of keypad are solved using different //approaches