c语言-leetcode题解之0076-minimum-window-substring.zip

#include <stdio.h> #include <stdlib.h> #include <string.h> /* sliding window pattern * while (r < size) { * // check target condition * while (target_condition) { * // calculate minimum length * // iterate left indicator * } * // iterate right indicator * } */ static char *minWindow(char *s, char *t) { int i, j, count[256] = { 0 }; int slen = strlen(s); int tlen = strlen(t); /* edges of sliding window */ int l = 0, r = 0; int min_len = slen + 1; int start = 0; int len = 0; for (i = 0; i < tlen; i++) { count[t[i]]++; } while (r < slen) { if (--count[s[r++]] >= 0) { /* pattern found */ len++; } while (len >= tlen) { if (r - l < min_len) { min_len = r - l; start = l; } /* Chars with negative count are not included in the pattern string */ if (++count[s[l++]] > 0) { len--; } } } char *result; if (min_len <= slen) { result = malloc(min_len + 1); memcpy(result, s + start, min_len); result[min_len] = '\0'; } else { result = ""; } return result; } int main(int argc, char **argv) { if (argc != 3) { fprintf(stderr, "Usage: ./test string pattern\n"); exit(-1); } printf("Answer: %s\n", minWindow(argv[1], argv[2])); return 0; }