aboutsummaryrefslogtreecommitdiff
path: root/concatenated_words.c
blob: 2278e5c500f921aa023a924e64c2875649f6451a (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
70
71
72
73
74
75
76
77
78
79
// 472. Concatenated Words
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 * given an array of strings 'words' (without duplicates), return all the
 * concatenated words in the given list of 'words'. a concatenated word is
 * defined as as string that is comprised entirely of at least two shorter
 * words in the given array.
 */

static int letterStarts[26];

int cmp(const void *a, const void *b) {
  char *wordA = *((char **)a);
  char *wordB = *((char **)b);
  if (wordA[0] != wordB[0])
    return wordA[0] - wordB[0];
  else
    return strlen(wordB) - strlen(wordA);
}

bool findWord(char **dict, int dictSize, char *word, int offset, int skipIdx) {
  int restLen = strlen(word + offset);
  if (restLen == 0)
    return true;
  char firstLetter = (word + offset)[0];
  int letterStartsIdx = firstLetter - 'a';
  int startDictIdx = letterStarts[letterStartsIdx];
  int endDictIdx = dictSize;
  if (startDictIdx == -1)
    return false;
  while (letterStartsIdx < 25) {
    letterStartsIdx++;
    if (letterStarts[letterStartsIdx] != -1)
      break;
  }
  if (firstLetter != 'z' && letterStarts[letterStartsIdx] != -1)
    endDictIdx = letterStarts[letterStartsIdx];
  for (int i = endDictIdx - 1; i >= startDictIdx; i--) {
    if (i == skipIdx)
      continue;
    int len = strlen(dict[i]);
    if (len == 0)
      continue;
    if (strncmp(dict[i], word + offset, len) == 0) {
      bool res = findWord(dict, dictSize, word, offset + len, skipIdx);
      if (res)
        return true;
    }
  }
  return false;
}

char **findAllConcatenatedWordsInADict(char **words, int wordsSize,
                                       int *returnSize) {
  char **ans = malloc(1000 * sizeof(char *));
  int ansCnt = 0;
  qsort(words, wordsSize, sizeof(char *), cmp);
  for (int i = 0; i < 26; i++)
    letterStarts[i] = -1;
  for (int i = 0; i < wordsSize; i++) {
    if (strlen(words[i]) == 0)
      continue;
    if (letterStarts[words[i][0] - 'a'] == -1)
      letterStarts[words[i][0] - 'a'] = i;
  }
  for (int i = 0; i < wordsSize; i++) {
    int len = strlen(words[i]);
    if (len && findWord(words, wordsSize, words[i], 0, i)) {
      ans[ansCnt] = malloc(len + 1);
      strcpy(ans[ansCnt++], words[i]);
    }
  }
  *returnSize = ansCnt;
  return ans;
}