aboutsummaryrefslogtreecommitdiff
path: root/letter_combo_number.c
blob: ae2c24786b269d813bed32cbfa501fa44b42f782 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
// 17. Letter Combinations of a Phone Number
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 * given a string containing digits 2 - 9 inclusive, return all possible letter
 * combinations that the number could represent. return the answer in any order.
 * a mapping of digits to letters (just like on the telephone buttons) is given
 * below [see image]. note that 1 does not map to any letters.
 */

char **letterCombinations(char *digits, int *return_size) {
  int len = strlen(digits);
  if (!len) {
    *return_size = 0;
    return NULL;
  }
  char pattern[10][5] = {"",    "",    "abc",  "def", "ghi",
                         "jkl", "mno", "pqrs", "tuv", "wxyz"};
  int *order = malloc(len * sizeof(int));
  int *curr = calloc(len, sizeof(int));
  curr[0] = -1;
  int l, size = 1, i, j;
  for (i = 0; i < len; i++) {
    l = strlen(pattern[digits[i] - '0']);
    size *= l;
    order[i] = l;
  }
  char **ans = (char **)malloc(size * sizeof(char *));
  for (i = 0; i < size; i++) {
    ans[i] = malloc((len + 1) * sizeof(char));
    curr[0]++;
    int id = 0;
    while (1) {
      if (curr[id] < order[id])
        break;
      else {
        curr[id + 1]++;
        curr[id] = curr[id] % order[id];
        id++;
      }
    }
    for (j = 0; j < len; j++)
      ans[i][j] = pattern[digits[j] - '0'][curr[j]];
    ans[i][len] = '\0';
  }
  *return_size = size;
  free(order), free(curr);
  return ans;
}

int main() {
  char d1[] = {"23"}, d2[] = {""}, d3[] = {"2"};
  int rs1[] = {}, rs2[] = {}, rs3[] = {};
  char **lc1 = letterCombinations(d1, rs1);
  char **lc2 = letterCombinations(d2, rs2);
  char **lc3 = letterCombinations(d3, rs3);
  for (int i = 0; i < 9; i++)
    printf("%s ",
           lc1[i]); // expect: "ad","ae","af","bd","be","bf","cd","ce","cf"
  printf("\n");
  for (int i = 0; i < 1; i++)
    printf("%s ", lc2[i]); // expect: NULL
  printf("\n");
  for (int i = 0; i < 3; i++)
    printf("%s ", lc3[i]); // expect: "a","b","c"
  printf("\n");
}