884. Uncommon Words from Two Sentences

A sentence is a string of single-space separated words where each word consists only of lowercase letters.

A word is uncommon if it appears exactly once in one of the sentences, and does not appear in the other sentence.

Given two sentences s1 and s2, return a list of all the uncommon words. You may return the answer in any order.
 

Example 1:

Input: s1 = “this apple is sweet”, s2 = “this apple is sour”
Output: [“sweet”,“sour”]
Explanation:
The word “sweet” appears only in s1, while the word “sour” appears only in s2.

Example 2:

Input: s1 = “apple apple”, s2 = “banana”
Output: [“banana”]

Constraints:

• 1 <= s1.length, s2.length <= 200
• s1 and s2 consist of lowercase English letters and spaces.
• s1 and s2 do not have leading or trailing spaces.
• All the words in s1 and s2 are separated by a single space.

From: LeetCode
Link: 884. Uncommon Words from Two Sentences

Solution:

Ideas:

• Tokenize each sentence by spaces (using a safe duplicate).

• Track per-word counts in s1 and s2.

• Collect words where (c1 == 1 && c2 == 0) || (c2 == 1 && c1 == 0).

• Return a newly allocated array of duplicated strings.

Code:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
typedef struct {
    char *word;
    int c1;  // count in s1
    int c2;  // count in s2
} Entry;

static char* my_strdup(const char* s) {
    size_t n = strlen(s);
    char* p = (char*)malloc(n + 1);
    if (!p) return NULL;
    memcpy(p, s, n + 1);
    return p;
}

static void add_word(Entry **arr, int *size, int *cap, const char *w, int which) {
    // find existing
    for (int i = 0; i < *size; ++i) {
        if (strcmp((*arr)[i].word, w) == 0) {
            if (which == 1) (*arr)[i].c1++;
            else (*arr)[i].c2++;
            return;
        }
    }
    // new entry
    if (*size == *cap) {
        int ncap = (*cap == 0) ? 16 : (*cap * 2);
        Entry *tmp = (Entry*)realloc(*arr, ncap * sizeof(Entry));
        if (!tmp) return; // out of memory (silent fail—contest style)
        *arr = tmp;
        *cap = ncap;
    }
    (*arr)[*size].word = my_strdup(w);
    (*arr)[*size].c1 = (which == 1) ? 1 : 0;
    (*arr)[*size].c2 = (which == 2) ? 1 : 0;
    (*size)++;
}

static void tokenize_and_count(const char *s, Entry **arr, int *size, int *cap, int which) {
    // work on a duplicate to use strtok
    char *dup = my_strdup(s);
    if (!dup) return;
    char *saveptr = NULL;
    char *tok = strtok_r(dup, " ", &saveptr);
    while (tok) {
        if (*tok != '\0') add_word(arr, size, cap, tok, which);
        tok = strtok_r(NULL, " ", &saveptr);
    }
    free(dup);
}

char** uncommonFromSentences(char* s1, char* s2, int* returnSize) {
    *returnSize = 0;
    Entry *entries = NULL;
    int n = 0, cap = 0;

    tokenize_and_count(s1, &entries, &n, &cap, 1);
    tokenize_and_count(s2, &entries, &n, &cap, 2);

    // First pass: count results
    int outCount = 0;
    for (int i = 0; i < n; ++i) {
        if ((entries[i].c1 == 1 && entries[i].c2 == 0) ||
            (entries[i].c2 == 1 && entries[i].c1 == 0)) {
            outCount++;
        }
    }

    char **ans = (char**)malloc(sizeof(char*) * outCount);
    if (!ans) {
        // clean up and return empty
        for (int i = 0; i < n; ++i) free(entries[i].word);
        free(entries);
        *returnSize = 0;
        return NULL;
    }

    // Second pass: fill results
    int k = 0;
    for (int i = 0; i < n; ++i) {
        if ((entries[i].c1 == 1 && entries[i].c2 == 0) ||
            (entries[i].c2 == 1 && entries[i].c1 == 0)) {
            ans[k++] = my_strdup(entries[i].word);
        }
    }

    // cleanup temp storage
    for (int i = 0; i < n; ++i) free(entries[i].word);
    free(entries);

    *returnSize = outCount;
    return ans;
}