leetcode

Leetcode Solutions (0x6A73)
git clone https://git.pngu.org/leetcode
Log | Files | Refs | Submodules | README

lexi_smallest_gen_str.c (2128B)

 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
// 3474. Lexicographically Smallest Generated String
#include "leetcode.h"

/*
 * you are given two strings 'str1' and 'str2' of lengths 'n' and 'm',
 * respectively. a string 'word' of length 'n + m - 1' is defined to be
 * generated by 'str1' and 'str2' if it satisfies the following conditions for
 * each index '0 <= i <= n - 1'. if 'str1[i] == T' the substring of 'word' with
 * size 'm' starting at index 'i' is equal to 'str2', ie. 'word[i .. (i + m -
 * 1)] == str2', and vice versa. return the lexicographically smallest possible
 * string that can be generated by 'str1' and 'str2'. if no string can be
 * generated, return an empty string.
 */

char *generateString(char *str1, char *str2) {
  int n = strlen(str1), m = strlen(str2), len = n + m - 1;
  char *s = (char *)malloc((len + 1) * sizeof(char));
  bool *fixed = (bool *)calloc(len, sizeof(bool));
  memset(s, 'a', len * sizeof(char));
  s[len] = '\0';
  for (int i = 0; i < n; i++)
    if (str1[i] == 'T')
      for (int j = i; j < i + m; j++) {
        if (fixed[j] && s[j] != str2[j - i]) {
          free(s);
          free(fixed);
          return "";
        } else {
          s[j] = str2[j - i];
          fixed[j] = true;
        }
      }
  for (int i = 0; i < n; i++)
    if (str1[i] == 'F') {
      bool flag = false;
      int idx = -1;
      for (int j = i + m - 1; j >= i; j--) {
        if (str2[j - i] != s[j])
          flag = 1;
        if (idx == -1 && !fixed[j])
          idx = j;
      }
      if (flag)
        continue;
      else if (idx != -1)
        s[idx] = 'b';
      else {
        free(s);
        free(fixed);
        return "";
      }
    }
  free(fixed);
  return s;
}

int main() {
  char *s11 = "TFTF", *s21 = "ab", *r1 = "ababa";
  char *s12 = "TFTF", *s22 = "abc", *r2 = "";
  char *s13 = "F", *s23 = "d", *r3 = "a";
  char *gs1 = generateString(s11, s21);
  char *gs2 = generateString(s12, s22);
  char *gs3 = generateString(s13, s23);
  printf("%s\n", gs1);
  assert(!strcmp(gs1, r1));
  printf("%s\n", gs2);
  assert(!strcmp(gs2, r2));
  printf("%s\n", gs3);
  assert(!strcmp(gs3, r3));
  free(gs1);
  free(gs3);
}