Facebook Interview Question
iOS DevelopersCountry: United States
Interview Type: In-Person
All permutations can be obtained by using recursion: obtaining letters for remaining digits and adding them to the tail of already obtained strings.
NSArray *allStringsForTelephoneNumberWithDigits(NSArray* digits,
NSUInteger startIndex, NSArray* baseStrings) {
if (startIndex == [digits count]) {
return baseStrings;
}
if (0 == [baseStrings count]) {
baseStrings = dict[digits[startIndex]];
} else {
NSArray* digitStrings = dict[digits[startIndex]];
if (0 != [digitStrings count]) {
NSMutableArray* newBaseStrings = [NSMutableArray array];
for (NSString* digitString in digitStrings) {
for (NSString* baseString in baseStrings) {
NSString* newBaseString =
[baseString stringByAppendingString:digitString];
[newBaseStrings addObject:newBaseString];
}
}
baseStrings = [NSArray arrayWithArray:newBaseStrings];
}
}
return allStringsForTelephoneNumberWithDigits(digits, startIndex + 1, baseStrings);
}
Sample:
allStringsForTelephoneNumberWithDigits(@[ @1, @1, @2, @1, @1, @8 ], 0, nil);
-(NSArray*)allPossibileStrings:(NSArray*)inputs
{
NSDictionary* dict = @{@2: @[@"A", @"B", @"C"],
@3: @[@"D", @"E", @"F"],
@4: @[@"G", @"H", @"I"],
@5: @[@"J", @"K", @"L"],
@6: @[@"M", @"N", @"O"],
@7: @[@"P", @"Q", @"R", @"S"],
@8: @[@"T", @"U", @"V"],
@9: @[@"W", @"X", @"Y", @"Z"]};
NSMutableArray *strings = [NSMutableArray array];
for (NSNumber *num in inputs) {
NSArray *letters = dict[num];
if ([strings count]==0) {
for (NSString *letter in letters) {
[strings addObject:letter];
}
}
else {
NSArray *copy = [strings copy];
[strings removeAllObjects];
for (NSString *string in copy) {
for (NSString *letter in letters) {
[strings addObject:[string stringByAppendingString:letter]];
}
}
}
}
return strings;
}
public class PhomeNumbers {
public static List<List<Character>> initData() {
List<List<Character>> list = new ArrayList<List<Character>>();
list.add(new ArrayList<Character>());//0
list.add(new ArrayList<Character>());//1
list.add(new ArrayList<Character>());//2
list.add(new ArrayList<Character>());//3
list.add(new ArrayList<Character>());//4
list.add(new ArrayList<Character>());//5
list.add(new ArrayList<Character>());//6
list.add(new ArrayList<Character>());//7
list.add(new ArrayList<Character>());//8
int j = 0;
for(int i = 0;i < 9;i++) {
for(int k =0;k < 3 && j < 26;k++,j++) {
list.get(i).add((char)('a' + j));
}
}
return list;
}
public static void sequence(int[] numbers,int pos,List<List<Character>> phone,char[] str) {
if(pos == numbers.length) {
for(Character ch : str) {
System.out.print(ch);
}
System.out.println();
return;
}
for(int i = 0;i < phone.get(pos).size();i++) {
str[pos] = phone.get(pos).get(i);
sequence(numbers,pos + 1,phone,str);
}
}
public static void main(String[] args) {
List<List<Character>> list = initData();
int[] numbers = new int[]{1,2};
char[] str = new char[numbers.length];
sequence(numbers,0,list,str);
}
}
NSMutableArray *result;
NSMutableString *tempSolution;
NSArray *dict;
void printAllPossibleCombo() {
dict = @[ @"",
@"",
@"ABC",
@"DEF",
@"GHI",
@"JKL",
@"MNO",
@"PQRS",
@"TUV",
@"WXYZ"];
result = [[NSMutableArray alloc] init];
tempSolution = [[NSMutableString alloc] init];
backtracking(@"234", 0);
for (NSString *s in result) {
NSLog(@"%@", s);
}
}
void backtracking(NSString *s, NSInteger i) {
NSString *setOfLetters = [dict objectAtIndex:([s characterAtIndex:i] - '0')];
for (NSInteger a = 0; a < [setOfLetters length]; a++) {
unichar ch = [setOfLetters characterAtIndex:a];
[tempSolution appendString: [NSString stringWithCharacters:&ch length:1]];
if (i == s.length - 1) {
[result addObject:[tempSolution copy]];
} else {
backtracking(s, i+1);
}
[tempSolution deleteCharactersInRange:NSMakeRange((tempSolution.length-1), 1)];
}
}
Implemented in PHP because why not :)
function phoneToText($phoneNumber) {
// storage for our found words
$foundWords = array();
// cast number / digits to a string, then to an array
$phoneDigits = str_split((string)$phoneNumber);
foreach ($phoneDigits as $digit) {
processDigit($digit, $foundWords);
}
return $foundWords;
}
function processDigit($digit, &$foundWords) {
// hash of phone digits to characters
static $numToCharHash = array(
2 => array('a', 'b', 'c'),
3 => array('d', 'e', 'f'),
4 => array('g', 'h', 'i'),
5 => array('j', 'k', 'l'),
6 => array('m', 'n', 'o'),
7 => array('p', 'q', 'r', 's'),
8 => array('t', 'u', 'v'),
9 => array('w', 'x', 'y', 'z')
);
// return if digit has no characters
if (!isset($numToCharHash[$digit])) {
return;
}
// if we have no existing entries, add current characters and return
if (count($foundWords) == 0) {
$foundWords = $numToCharHash[$digit];
return;
}
// append the first char to each word
for ($j = 0, $wordsLen = count($foundWords); $j < $wordsLen; $j++) {
$t = $foundWords[$j];
// first, append the existing entry with the first char
$foundWords[$j] .= $numToCharHash[$digit][0];
// add new entries for the other chars
for ($i = 1, $charCount = count($numToCharHash[$digit]); $i < $charCount; $i++) {
$foundWords[] = $t . $numToCharHash[$digit][$i];
}
}
return;
}
python
def combinations(sofar,phno,numpad):
if phno == '' or phno is None:
print sofar
return
for dig in phno:
options = numpad[int(dig)]
for op in options:
combinations(sofar+op,phno[1:],numpad)
numpad = {2: ["A", "B", "C"],
3: ["D", "E", "F"],
4: ["G", "H", "I"],
5: ["J", "K", "L"],
6: ["M", "N", "O"],
7: ["P", "Q", "R", "S"],
8: ["T", "U", "V"],
9: ["W", "X", "Y", "Z"]};
combinations('','23',numpad)
-(NSArray*)allPossibileStrings:(NSArray*)inputs
{
NSDictionary* dict = @{@2: @[@"A", @"B", @"C"],
@3: @[@"D", @"E", @"F"],
@4: @[@"G", @"H", @"I"],
@5: @[@"J", @"K", @"L"],
@6: @[@"M", @"N", @"O"],
@7: @[@"P", @"Q", @"R", @"S"],
@8: @[@"T", @"U", @"V"],
@9: @[@"W", @"X", @"Y", @"Z"]};
NSMutableArray *strings = [NSMutableArray array];
for (NSNumber *num in inputs) {
NSArray *letters = dict[num];
if ([strings count]==0) {
for (NSString *letter in letters) {
[strings addObject:letter];
}
}
else {
NSArray *copy = [strings copy];
[strings removeAllObjects];
for (NSString *string in copy) {
for (NSString *letter in letters) {
[strings addObject:[string stringByAppendingString:letter]];
}
}
}
}
return strings;
}
Assume that the phone number is supplied as a string (e.g. @"123")
+(NSArray*) phoneStrings:(NSString*)number
{
return [self phoneStrings:number andOffset:0];
}
+(NSArray*) phoneStrings:(NSString*)number andOffset:(int)offset
{
NSMutableArray* retval = [[NSMutableArray alloc] init];
int n = (int)[number characterAtIndex:offset] - '0';
NSArray* digits = [dict objectForKey:@(n)];
for (NSString* charString in digits)
{
NSString* head = charString;
if (number.length - offset > 1)
{
NSArray* tails = [self phoneStrings:number andOffset:offset + 1];
for (NSString* tail in tails)
{
NSString* s = [head stringByAppendingString:tail];
[retval addObject:s];
}
}
else
{
[retval addObject:head];
}
}
return retval;
}
Python Without Recursion
def phone_number(number):
keypad = {2: ['A', 'B', 'C'],
3: ['D', 'E', 'F'],
4: ['G', 'H', 'I'],
5: ['J', 'K', 'L'],
6: ['M', 'N', 'O'],
7: ['P', 'Q', 'R', 'S'],
8: ['T', 'U', 'V'],
9: ['W', 'X', 'Y', 'Z']}
letter_combination = []
for digit in number:
if digit == 1:
letters = []
else:
letters = keypad[digit]
if not letter_combination:
# initialize the combination with the letters of first digit
letter_combination.extend([[letter] for letter in letters])
continue
else:
for combi in letter_combination[:]:
letter_combination.remove(combi)
for letter in letters:
x = combi[:]
x.append(letter)
letter_combination.append(x)
print letter_combination
Working:
Initialize the combinations with each letter for the first digit
letter_combination.extend([[letter] for letter in letters])
Then for each additional digit
for letter in letters:
x = combi[:]
x.append(letter)
letter_combination.append(x)
this will create a copy of the combination in the list of combinations (without modifying the original. Also note we remove the existing one here
letter_combination.remove(combi)
we remove this because
combination = a b c
if next digit it 3 then
remove A
create a copy of A (ie x)
then append d e f to A one by one and add it to list
thus letter_combination becomes
ad ae af b c
then remove b and repeat
ad ae af bd be bf
and so on..
In scala
object Main extends App {
import scala.util.Random
val dict = Seq("ABC","DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ")
val number = Random.nextInt(1000000)
def ntos(input:Int):Seq[String] = {
input match {
case n if n<2 => Seq("")
case n if n<10 => dict(n-2).map(c=>""+c).toSeq //dict indexs start at 2
case n =>
val rec = ntos(n/10)
val ret = dict(n%10-2).map(c=>rec.map(r=>r+c)).flatMap(identity)
ret.toSeq
}
}
ntos(number).foreach(n=>println(number, n))
}
Bug fix. Digits 0 and 1 are ignored.
object T9 extends App {
import scala.util.Random
val dict = Seq("ABC","DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ")
val number = Math.abs(Random.nextInt)+2
def ntos(input:Int):Seq[String] = {
input match {
case n if n<2 => Seq("")
case n if n<10 => dict(n-2).map(c=>""+c).toSeq //dict indexs start at 2
case n =>
val rec = ntos(n/10)
val ret = n%10-2 match {
case x if x>=0 => dict(x).map(c=>rec.map(r=>r+c)).flatMap(identity)
case _ => rec
}
ret.toSeq
}
}
ntos(number).foreach(n=>println(number, n))
}
- (NSArray *)getLetterCombinationFromPhoneNumber:(NSDictionary *)dict PhoneNumber:(NSString *)number
{
NSMutableArray *letters = [NSMutableArray array];
for(int i=0;i<[number length];i++)
{
unichar ch = [number characterAtIndex:i];
NSNumber *key = [NSNumber numberWithInteger:[[NSString stringWithFormat:@"%c",ch] integerValue]];
[letters addObjectsFromArray:dict[key]];
}
NSLog(@"getLetterCombinationFromPhoneNumber : %@",letters);
return letters;
}
[self getLetterCombinationFromPhoneNumber:@{@2: @[@"A", @"B", @"C"],
@3: @[@"D", @"E", @"F"],
@4: @[@"G", @"H", @"I"],
@5: @[@"J", @"K", @"L"],
@6: @[@"M", @"N", @"O"],
@7: @[@"P", @"Q", @"R", @"S"],
@8: @[@"T", @"U", @"V"],
@9: @[@"W", @"X", @"Y", @"Z"]} PhoneNumber:@"1234"];
/*OUTPUT:
(
A,
B,
C,
D,
E,
F,
G,
H,
I
)
*/
static HashMap<Integer, char[]> dictionary;
public static void main(String[] args){
dictionary = new HashMap<>();
char[] tmp0={'0','1','2'};
char[] tmp1={'a','b','c'};
char[] tmp2={'d','e','f'};
char[] tmp3={'h','i','j'};
char[] tmp4={'k','l','m'};
char[] tmp5={'o','p','q'};
char[] tmp6={'r','s','t'};
char[] tmp7={'u','v','w'};
char[] tmp8={'x','y','z'};
dictionary.put(1,tmp0);
dictionary.put(2,tmp1);
dictionary.put(3,tmp2);
dictionary.put(4,tmp3);
dictionary.put(5,tmp4);
dictionary.put(6,tmp5);
dictionary.put(7,tmp6);
dictionary.put(8,tmp7);
dictionary.put(9,tmp8);
int[] number={9,1,8,9,8,3,8,4};
solve(null,number);
}
static void solve(String[] c,int[] number){
if(number==null)
return;
else{
char[] c2=dictionary.get(number[0]);
String[] c3;
if(c!=null)
c3=new String[c.length*c2.length];
else
c3=new String[1*c2.length];
int count=0;
if(c!=null){
for(int i=0;i<c.length;i++){
for(int j=0;j<c2.length;j++){
c3[count++]=String.valueOf(c[i])+String.valueOf(c2[j]);
}
}
}else{
for(int j=0;j<c2.length;j++){
c3[count++]=String.valueOf(c2[j]);
}
}
int[] next=new int[number.length-1];
for(int i=1;i<number.length;i++){
next[i-1]=number[i];
}
if(next.length<1){
for(int i=0;i<c3.length;i++){
System.out.println(c3[i]);
}
}
else
solve(c3,next);
}
}
objective c version using recursion and blocks:
typedef void (^numbersBlock)(NSString *word);
void getSubstrings(NSDictionary *pattern,
NSMutableArray *input,
NSString *word,
numbersBlock block) {
if ([input count] == 0) {
block(word);
} else {
NSString *inputKey = [input objectAtIndex:0];
NSMutableArray *copiedInput = [input mutableCopy];
[copiedInput removeObjectAtIndex:0];
NSNumber *number = [NSNumber numberWithInteger:[inputKey integerValue]];
NSArray *letters = pattern[number];
if (letters) {
for (int i = 0; i < [letters count]; i++) {
NSString *character = letters[i];
NSString *newWord = [word stringByAppendingString:character];
getSubstrings(pattern, copiedInput, newWord, block);
}
} else {
getSubstrings(pattern, copiedInput, word, block);
}
}
}
int main (int argc, const char * argv[])
{
@autoreleasepool {
NSDictionary* dict = @{@2: @[@"A", @"B", @"C"],
@3: @[@"D", @"E", @"F"],
@4: @[@"G", @"H", @"I"],
@5: @[@"J", @"K", @"L"],
@6: @[@"M", @"N", @"O"],
@7: @[@"P", @"Q", @"R", @"S"],
@8: @[@"T", @"U", @"V"],
@9: @[@"W", @"X", @"Y", @"Z"]};
NSString *inputPhone = @"25349";
NSMutableArray *characters = [NSMutableArray array];
for (int i = 0; i < inputPhone.length; i++) {
NSString *substring = [inputPhone
substringWithRange:NSMakeRange(i, 1)];
[characters addObject:substring] ;
}
getSubstrings(dict, characters, @"", ^(NSString *word) {
NSLog(@"%@", word);
});
}
}
+ (NSArray *) allPossibleWordsFromNumber:(NSNumber *)number andDictionary:(NSDictionary *)dict{
if (number == nil || dict == nil || [number integerValue] < 2){
return nil;
}
if ([number integerValue] < 10) {
return dict[number];
}
NSString *digits = [number stringValue];
NSInteger key = [[digits substringToIndex:1] integerValue];
NSMutableSet *results = [NSMutableSet setWithArray:dict[@(key)]];
digits = [digits substringFromIndex:1];
while (digits.length) {
NSInteger c = [[digits substringToIndex:1] integerValue];
NSArray *nextChars = dict[@(c)];
for (NSString *word in [results copy]) { //for each word already produced
for (NSString *w in nextChars) { //for new character
[results addObject:[word stringByAppendingString:w]];
[results removeObject:word];
}
}
digits = [digits substringFromIndex:1];
}
NSLog(@"possible words: %@", [[results allObjects] sortedArrayUsingSelector:@selector(localizedCaseInsensitiveCompare:)]);
return results;
}
@interface PhoneNumbersToWords ()
@property (nonatomic, strong) NSDictionary *keypadDictionary;
@end
@implementation PhoneNumbersToWords
- (NSDictionary*)keypadDictionary
{
if (_keypadDictionary == nil)
{
_keypadDictionary = @{@"2": @[@"A", @"B", @"C"],
@"3": @[@"D", @"E", @"F"],
@"4": @[@"G", @"H", @"I"],
@"5": @[@"J", @"K", @"L"],
@"6": @[@"M", @"N", @"O"],
@"7": @[@"P", @"Q", @"R", @"S"],
@"8": @[@"T", @"U", @"V"],
@"9": @[@"W", @"X", @"Y", @"Z"]};
}
return _keypadDictionary;
}
- (NSArray*)allWordsFromNumber:(NSString*)phoneNumber
{
NSArray *allWords = [[NSMutableArray alloc]init];
for (int a = 0; a < phoneNumber.length; a++)
{
NSString *currentCharacter = [phoneNumber substringWithRange:NSMakeRange(a, 1)];
NSArray *charactersForNumber = [self.keypadDictionary objectForKey:currentCharacter];
NSMutableArray *newWords = [[NSMutableArray alloc]init];
for (NSString *numberCharacter in charactersForNumber)
{
if (allWords.count > 0)
{
for (NSString *existingString in allWords)
{
[newWords addObject:[NSString stringWithFormat:@"%@%@", existingString, numberCharacter]];
}
}
else
{
[newWords addObject:numberCharacter];
}
}
allWords = [NSArray arrayWithArray:newWords];
}
return [NSArray arrayWithArray:allWords];
}
public static void Test_0() {
Map<String, String[]> map = Maps.newHashMap();
map.put("2", new String[]{"A", "B", "C"});
map.put("3", new String[]{"D", "E", "F"});
map.put("4", new String[]{"G", "H", "I"});
map.put("5", new String[]{"J", "K", "L"});
map.put("6", new String[]{"M", "N", "O"});
map.put("7", new String[]{"P", "Q", "R", "S"});
map.put("8", new String[]{"T", "U", "V"});
map.put("9", new String[]{"W", "X", "Y", "Z"});
String input = "4255387856";
List answer = solve(map, input, Lists.newArrayList(""));
System.out.println(answer.size());
}
private static List<String> solve(Map<String, String[]> map, String input, List<String> current) {
if ((input == null) || (input.isEmpty())) {
return current;
}
String[] values = map.get(input.charAt(0) + "");
List<String> next = Lists.newArrayList();
for (String choice : current) {
for (String value : values) {
next.add(choice + value);
}
}
return solve(map, input.substring(1), next);
}
@interface PhoneToAlphaCombos : NSObject
@property (nonatomic) NSString *number;
- (instancetype)initWithPhoneNumber:(NSString*)phoneNumber;
- (NSArray*)allAlphaCombinations;
@end
@implementation PhoneToAlphaCombos
- (instancetype)initWithPhoneNumber:(NSString*)phoneNumber {
self = [super init];
if (self) {
self.number = [[phoneNumber componentsSeparatedByCharactersInSet:[NSCharacterSet characterSetWithCharactersInString:@"()- "]] componentsJoinedByString:@""];
}
return self;
}
- (NSArray*)allAlphaCombinations {
NSArray *digits = [self characterArrayForString:self.number];
NSArray *allCombos = [NSArray array];
for (NSInteger i = [digits count] - 1; i >= 0; i--) {
NSNumber *digitNumber = @([[digits objectAtIndex:i] integerValue]);
if (i + 1 == [digits count]) {
allCombos = [self lettersForDigit:digitNumber];
} else {
allCombos= [self wordSetsByMergingWordSet:[self lettersForDigit:digitNumber] withwordSet:allCombos];
}
}
return allCombos;
}
- (NSArray*)wordSetsByMergingWordSet:(NSArray*)s1 withwordSet:(NSArray*)s2 {
NSMutableArray *mergedSet = [NSMutableArray array];
for (NSInteger i = 0; i < [s1 count]; i++) {
for (NSInteger j = 0; j < [s2 count]; j++) {
[mergedSet addObject:[NSString stringWithFormat:@"%@%@", [s1 objectAtIndex:i], [s2 objectAtIndex:j]]];
}
}
return mergedSet;
}
- (NSArray*)lettersForDigit:(NSNumber*)digit {
NSDictionary* dict = @{@2: @[@"A", @"B", @"C"],
@3: @[@"D", @"E", @"F"],
@4: @[@"G", @"H", @"I"],
@5: @[@"J", @"K", @"L"],
@6: @[@"M", @"N", @"O"],
@7: @[@"P", @"Q", @"R", @"S"],
@8: @[@"T", @"U", @"V"],
@9: @[@"W", @"X", @"Y", @"Z"]};
NSArray *lettersArray = [dict objectForKey:digit];
return lettersArray;
}
- (NSArray*)characterArrayForString:(NSString*)string {
NSMutableArray *array = [NSMutableArray array];
NSRange range = {0, 1};
for (NSInteger i = 0; i < [string length]; i++) {
range.location = i;
[array addObject:[string substringWithRange:range]];
}
return array;
}
@end
var dict : Dictionary<Int,[String]> = [2:["A","B","C"],3:["D","E","F"],4:["G","H","I"],5:["J","K","L"],6:["M","N","O"],7:["P","Q","R","S"],8:["T","U","V"],9:["W","X","Y","Z"]];
func findAlphabetsInNumber(number:String){
var arr : [Character] = [Character]()
var dictVals : Dictionary<Int,[String]> = Dictionary()
for val in number{
if val != "1" && val != "0" {
arr.append(val)
}
for (__,val) in enumerate(arr){
let num = String(val).toInt()
dictVals[num!] = dict[num!]!
arr.removeAtIndex(0)
break
}
}
println(dictVals)
}
//This is a dfs problem
NSDictionary* phoneDict=@{//data};
NSString* number=@"1234";
-(void) combinationString:(NSString*)string index:(NSUInteger)index result:(NSMutableArray*)result{
if(index==[number length]){
[result addObject:string];
return;
}
for(NSString* x in dict[index+1]){
NSString* newString=[string stringByAppendString:x];
[self combinationString:newString index:index+1 result:result];
}
}
Soln:-
1) Get the key/value from dictionary.
2) Combine all values into 1 single array of letters.
3) Permutate the single array to get all letter combinations for input phoneNumber.
Code:-
-(void)allPossibileStrings:(NSArray*)inputs
{
NSDictionary* dict = @{@2: @[@"A", @"B", @"C"],
@3: @[@"D", @"E", @"F"],
@4: @[@"G", @"H", @"I"],
@5: @[@"J", @"K", @"L"],
@6: @[@"M", @"N", @"O"],
@7: @[@"P", @"Q", @"R", @"S"],
@8: @[@"T", @"U", @"V"],
@9: @[@"W", @"X", @"Y", @"Z"]};
NSMutableArray *combineLetters = [NSMutableArray array];
//Loop through phoneNumbers entered
for (NSNumber *num in inputs) {
//Get Value for each PhoneNumber from it's key
NSArray *letters = dict[num];
for (NSArray *tempArray in letters) {
//Get all letters and store in combineLettersArray
[combineLetters addObject:tempArray];
}
}
NSLog(@"The Combined Letter is %@", combineLetters);
//Get Permutation of letters from array
[self getPermutationFromInput:combineLetters];
}
//Permutation Function
- (void)getPermutationFromInput : (NSMutableArray *)inputArray {
NSMutableArray *permutation = nil;
for (int i = 0; i < inputArray.count; i++) {
if (!permutation) {
permutation = [NSMutableArray new];
for (NSString *character in inputArray) {
[permutation addObject:[NSArray arrayWithObject:character]];
}
} else {
NSMutableArray *aCopy = [permutation copy];
[permutation removeAllObjects];
for (NSString *character in inputArray) {
for (NSArray *tempArray in aCopy) {
if ([tempArray containsObject:character] == NO) {
NSMutableArray *newArray = [NSMutableArray arrayWithArray:tempArray];
[newArray addObject:character];
[permutation addObject:newArray];
}
}
}
}
}
NSLog(@"Permutation from Input is \n %@", permutation);
}
How to use Code:-
[self allPossibileStrings:@[@2,@4,@5]];
//In the Above the numbers on the keypads are 2,4 and 5.
Soln:-
1) Get the key/value from dictionary.
2) Combine all values into 1 single array of letters.
3) Permutate the single array to get all letter combinations for input phoneNumber.
Code:-
-(void)allPossibileStrings:(NSArray*)inputs
{
NSDictionary* dict = @{@2: @[@"A", @"B", @"C"],
@3: @[@"D", @"E", @"F"],
@4: @[@"G", @"H", @"I"],
@5: @[@"J", @"K", @"L"],
@6: @[@"M", @"N", @"O"],
@7: @[@"P", @"Q", @"R", @"S"],
@8: @[@"T", @"U", @"V"],
@9: @[@"W", @"X", @"Y", @"Z"]};
NSMutableArray *combineLetters = [NSMutableArray array];
//Loop through phoneNumbers entered
for (NSNumber *num in inputs) {
//Get Value for each PhoneNumber from it's key
NSArray *letters = dict[num];
for (NSArray *tempArray in letters) {
//Get all letters and store in combineLettersArray
[combineLetters addObject:tempArray];
}
}
NSLog(@"The Combined Letter is %@", combineLetters);
//Get Permutation of letters from array
[self getPermutationFromInput:combineLetters];
}
//Permutation Function
- (void)getPermutationFromInput : (NSMutableArray *)inputArray {
NSMutableArray *permutation = nil;
for (int i = 0; i < inputArray.count; i++) {
if (!permutation) {
permutation = [NSMutableArray new];
for (NSString *character in inputArray) {
[permutation addObject:[NSArray arrayWithObject:character]];
}
} else {
NSMutableArray *aCopy = [permutation copy];
[permutation removeAllObjects];
for (NSString *character in inputArray) {
for (NSArray *tempArray in aCopy) {
if ([tempArray containsObject:character] == NO) {
NSMutableArray *newArray = [NSMutableArray arrayWithArray:tempArray];
[newArray addObject:character];
[permutation addObject:newArray];
}
}
}
}
}
NSLog(@"Permutation from Input is \n %@", permutation);
}
How to use Code:-
[self allPossibileStrings:@[@2,@4,@5]];
//In the Above the numbers on the keypads are 2,4 and 5.
- (void)printAllWordsGivenPhoneNumber:(NSString *)number
{
if (!number.length) {
NSLog(@"Non valid number!");
}
NSDictionary *dict = @{@2: @[@"A", @"B", @"C"],
@3: @[@"D", @"E", @"F"],
@4: @[@"G", @"H", @"I"],
@5: @[@"J", @"K", @"L"],
@6: @[@"M", @"N", @"O"],
@7: @[@"P", @"Q", @"R", @"S"],
@8: @[@"T", @"U", @"V"],
@9: @[@"W", @"X", @"Y", @"Z"]};
[self recursePrint:@"" number:number currentIndex:0 dictionary:dict];
}
- (void)recursePrint:(NSString *)current number:(NSString *)number currentIndex:(int)index dictionary:(NSDictionary *)dictionary
{
if (index == number.length) {
NSLog(@"%@", current);
}
else {
NSString *numString = [number substringWithRange:NSMakeRange(index, 1)];
NSArray *letters = dictionary[@([numString intValue])];
if (letters) {
for (NSString *letter in letters) {
NSString *updatedString = [current stringByAppendingString:letter];
[self recursePrint:updatedString number:number currentIndex:index + 1 dictionary:dictionary];
}
}
else {
// The case for 0, 1 and other character not in dictionary.
[self recursePrint:current number:number currentIndex:index + 1 dictionary:dictionary];
}
}
}
Much simpler when broke out into several methods I think
+(void)testRun {
NSLog(@"%@",[self wordFromPhoneNumber:@423]);
}
+(NSArray*)wordFromPhoneNumber:(NSNumber*)phoneNum {
NSDictionary *phoneDict = @{@2: @[@"A", @"B", @"C"],
@3: @[@"D", @"E", @"F"],
@4: @[@"G", @"H", @"I"],
@5: @[@"J", @"K", @"L"],
@6: @[@"M", @"N", @"O"],
@7: @[@"P", @"Q", @"R", @"S"],
@8: @[@"T", @"U", @"V"],
@9: @[@"W", @"X", @"Y", @"Z"]};
NSString *numberString = phoneNum.stringValue;
NSMutableArray *numberArray = [NSMutableArray new];
NSNumberFormatter *nf = [NSNumberFormatter new];
for (int i = 0; i < numberString.length; i++) {
[numberArray addObject:[nf numberFromString:[NSString stringWithFormat:@"%c", [numberString characterAtIndex:i]]]];
}
NSMutableArray *letterArray = [NSMutableArray new];
for (NSNumber *number in numberArray) {
if ([phoneDict.allKeys containsObject:number]) {
NSLog(@"%@", number);
[letterArray addObject:phoneDict[number]];
}
}
return [self combineAllArrays:letterArray index:0];
}
+(NSArray*)combineAllArrays:(NSArray*)arrays index:(int)index {
NSArray *arrayToCombine = arrays[index];
while (index < arrays.count - 1) {
index += 1;
arrayToCombine = [self combineArraysWithArrayA:arrayToCombine andArrayB:arrays[index]];
}
return arrayToCombine;
}
+(NSArray*)combineArraysWithArrayA:(NSArray*)a andArrayB:(NSArray*)b {
NSMutableArray *finalArray = [NSMutableArray new];
for (NSString* itemA in a) {
for (NSString *itemB in b) {
NSString *string = [NSString stringWithFormat:@"%@%@",itemA,itemB];
[finalArray addObject:string];
}
}
return finalArray;
}
func telephoneKeyPad(input : Int) {
var dicArray = [Dictionary<Int, [String]>]()
let number2 = [2 : ["A","B","C"]]
let number3 = [3 : ["D","E","F"]]
let number4 = [4 : ["G","H","I"]]
let number5 = [5 : ["J","K","L"]]
let number6 = [6 : ["M","N","0"]]
let number7 = [7 : ["P","Q","R","S"]]
let number8 = [8 : ["T","U", "V"]]
let number9 = [9 : ["W","X","Y", "Z"]]
dicArray.append(number2)
dicArray.append(number3)
dicArray.append(number4)
dicArray.append(number5)
dicArray.append(number6)
dicArray.append(number7)
dicArray.append(number8)
dicArray.append(number9)
var tempPhoneNumberArray = [String]()
var tempStringArray = [String]()
var phonekeyPadInput = String(String(input).characters)
for value in phonekeyPadInput.characters {
tempPhoneNumberArray.append(String(value))
}
var currentIndexInTempArray = 0
while currentIndexInTempArray < tempPhoneNumberArray.count {
//Get the key for the number in the Dictionary
let indexElement = Int(tempPhoneNumberArray[currentIndexInTempArray])! - 2
let letterArray = dicArray[indexElement][Int(tempPhoneNumberArray[currentIndexInTempArray])!]
print("LetterArray = \(letterArray!)")
for value in letterArray! {
//Add all the combinations into 1 tempArray
tempStringArray.append(value)
}
currentIndexInTempArray += 1
}
print("TempStringArray = \(tempStringArray)")
let finalResult = combineLetters(inputArray: tempStringArray)
print("The Letter combination is \(finalResult)")
}
func combineLetters(inputArray: [String]) -> [String]{
var anchorPoint = 0
var nextIndex = 1
var outputArray = [String]()
while anchorPoint < inputArray.count {
//Do not add duplicates letters like AA or BB
if anchorPoint != nextIndex {
outputArray.append("\(inputArray[anchorPoint]) \(inputArray[nextIndex])")
}
if inputArray[nextIndex] != inputArray.last {
nextIndex += 1
} else {
anchorPoint += 1
nextIndex = 0
}
}
return outputArray
}
func telephoneKeyPad(input : Int) {
var dicArray = [Dictionary<Int, [String]>]()
let number2 = [2 : ["A","B","C"]]
let number3 = [3 : ["D","E","F"]]
let number4 = [4 : ["G","H","I"]]
let number5 = [5 : ["J","K","L"]]
let number6 = [6 : ["M","N","0"]]
let number7 = [7 : ["P","Q","R","S"]]
let number8 = [8 : ["T","U", "V"]]
let number9 = [9 : ["W","X","Y", "Z"]]
dicArray.append(number2)
dicArray.append(number3)
dicArray.append(number4)
dicArray.append(number5)
dicArray.append(number6)
dicArray.append(number7)
dicArray.append(number8)
dicArray.append(number9)
var tempPhoneNumberArray = [String]()
var tempStringArray = [String]()
var phonekeyPadInput = String(String(input).characters)
for value in phonekeyPadInput.characters {
tempPhoneNumberArray.append(String(value))
}
var currentIndexInTempArray = 0
while currentIndexInTempArray < tempPhoneNumberArray.count {
//Get the key for the number in the Dictionary
let indexElement = Int(tempPhoneNumberArray[currentIndexInTempArray])! - 2
let letterArray = dicArray[indexElement][Int(tempPhoneNumberArray[currentIndexInTempArray])!]
print("LetterArray = \(letterArray!)")
for value in letterArray! {
//Add all the combinations into 1 tempArray
tempStringArray.append(value)
}
currentIndexInTempArray += 1
}
print("TempStringArray = \(tempStringArray)")
let finalResult = combineLetters(inputArray: tempStringArray)
print("The Letter combination is \(finalResult)")
}
func combineLetters(inputArray: [String]) -> [String]{
var anchorPoint = 0
var nextIndex = 1
var outputArray = [String]()
while anchorPoint < inputArray.count {
//Do not add duplicates letters like AA or BB
if anchorPoint != nextIndex {
outputArray.append("\(inputArray[anchorPoint]) \(inputArray[nextIndex])")
}
if inputArray[nextIndex] != inputArray.last {
nextIndex += 1
} else {
anchorPoint += 1
nextIndex = 0
}
}
return outputArray
}
- pratikrd April 24, 2014