[C, C++, Java, Python3] 2 Approach: Hash Table and Trie
Solution 1 (Hash Table)\n## Intuition\nThe task requires identifying uncommon words from two sentences. An uncommon word is one that appears exactly once in one
# Solution 1 (Hash Table)\n## Intuition\nThe task requires identifying uncommon words from two sentences. An uncommon word is one that appears exactly once in one of the sentences and does not appear in the other. A hash table is well-suited for counting occurrences of words in both sentences, as it provides fast lookups and updates.\n\n## Approach\n1. **Hash Table:** Use a hash table to store each word and its count. Traverse through both strings and add the words to the hash table. Increment the count for each word every time it\'s found.\n2. **Result Construction:** After processing both strings, traverse the hash table to collect the words that have a count of exactly `1`. These words are the uncommon ones.\n3. **Return:** Return the array of these uncommon words.\n\n## Complexity\nLet `n` and `m` be the length of string `s1` and `s2` respectively.\n- Time complexity: $$O(n + m)$$\n    - Traverse string `s1`: $$O(n)$$\n    - Traverse string `s2`: $$O(m)$$\n    - Traverse hash table containing each unique word from `s1` and `s2`: $$O(n + m)$$\n- Space complexity: $$O(n + m)$$\n    - Hash Table containing each unique word from `s1` and `s2`: $$O(n + m)$$\n    - Other auxiliary variables: $$O(1)$$\n## Code\n```c []\nstruct HashTable {\n    char *word;\n    uint8_t count; \n    UT_hash_handle hh;\n};\n\nvoid insertWord(struct HashTable** hashTable, char* word, int8_t wordLen){\n    struct HashTable *item = (struct HashTable*)malloc(sizeof(struct HashTable));\n    item->word = (char*)malloc(wordLen + 1);\n\n    for(uint8_t i = 0; i <= wordLen; i++)\n        item->word[i] = word[i];\n    item->count = 1;\n\n    HASH_ADD_STR(*hashTable, word, item);\n}\n\nvoid scanString(struct HashTable** hashTable, char* s, int *returnSize){\n    struct HashTable *item;\n    char *entry = (char*)malloc(201);\n    uint8_t wordLen = 0;\n\n    for(uint8_t i = 0; s[i]; i++){\n        if(s[i] != \' \') entry[wordLen++] = s[i];\n        else{\n            entry[wordLen] = \'\\0\';\n            HASH_FIND_STR(*hashTable, entry, item);\n\n            if(!item) insertWord(&(*hashTable), entry, wordLen), (*returnSize)++;\n            else if(item->count++ == 1) (*returnSize)--;\n\n            wordLen = 0;\n        }\n    }\n\n    entry[wordLen] = \'\\0\';\n    HASH_FIND_STR((*hashTable), entry, item);\n\n    if(!item) insertWord(&(*hashTable), entry, wordLen), (*returnSize)++;\n    else if(item->count++ == 1) (*returnSize)--;\n    \n    free(entry);\n}\n\nchar** uncommonFromSentences(char* s1, char* s2, int* returnSize) {\n    struct HashTable *hashTable = NULL, *item, *tmp;\n    *returnSize = 0;\n\n    scanString(&hashTable, s1, returnSize);\n    scanString(&hashTable, s2, returnSize);\n\n    char **res = (char**)malloc(sizeof(char*) * (*returnSize));\n    uint8_t i = 0;\n\n    HASH_ITER(hh, hashTable, item, tmp){\n        if(item->count == 1)\n            res[i++] = item->word;\n        else free(item->word);\n\n        HASH_DEL(hashTable, item);\n        free(item);\n    }\n\n    return res;\n}\n```\n``` cpp []\nclass Solution {\npublic:\n    vector<string> uncommonFromSentences(string s1, string s2) {\n        unordered_map<string, uint8_t> hashTable;\n\n        scanString(hashTable, s1);\n        scanString(hashTable, s2);\n\n        vector<string> res;\n\n        for (const auto& item : hashTable)\n            if(item.second == 1) res.push_back(item.first);\n\n        return res;\n    }\n\n    void scanString(unordered_map<string, uint8_t>& hashTable, string& s){\n        string entry;\n\n        for(const char& ch : s){\n            if(ch != \' \') entry.push_back(ch);\n            else{\n                hashTable[entry]++;\n                entry.clear();\n            }\n        }\n\n        hashTable[entry]++;\n    }\n};\n```\n``` java []\nclass Solution {\n    public String[] uncommonFromSentences(String s1, String s2) {\n        HashMap<String, Short> hashTable = new HashMap<>();\n\n        short returnSize = 0;\n\n        returnSize += scanString(hashTable, s1);\n        returnSize += scanString(hashTable, s2);\n\n        String[] res = new String[returnSize];\n        short i = 0;\n\n        for(Map.Entry<String, Short> item : hashTable.entrySet())\n            if(item.getValue() == 1) res[i++] = item.getKey();\n\n        return res;\n    }\n\n    short scanString(HashMap<String, Short> hashTable, String s){\n        StringBuilder entry = new StringBuilder("");\n        String str;\n        short count, returnSize = 0;\n\n        for(short i = 0, n = (short) s.length(); i < n; i++){\n            if(s.charAt(i) != \' \') entry.append(s.charAt(i));\n            else{\n                str = entry.toString();\n                count = hashTable.getOrDefault(str, (short) 0);\n\n                if(count == 0) returnSize++;\n                else if(count == 1) returnSize--;\n\n                hashTable.put(str, (short) (count + 1));\n                entry.setLength(0);\n            }\n        }\n\n        str = entry.toString();\n        count = hashTable.getOrDefault(str, (short) 0);\n\n        if(count == 0) returnSize++;\n        else if(count == 1) returnSize--;\n\n        hashTable.put(str, (short) (count + 1));\n\n        return returnSize;\n    }\n}\n```\n``` python3 []\nclass Solution:\n    def uncommonFromSentences(self, s1: str, s2: str) -> List[str]:\n        def scanString(hashTable, s):\n            entry = ""\n\n            for ch in s:\n                if ch != \' \': entry += ch\n                else:\n                    if entry not in hashTable:\n                        hashTable[entry] = 1\n                    else: hashTable[entry] += 1\n\n                    entry = ""\n\n            if entry not in hashTable:\n                hashTable[entry] = 1\n            else: hashTable[entry] += 1\n\n                \n        hashTable = {}\n        \n        scanString(hashTable, s1)\n        scanString(hashTable, s2)\n\n        res = []\n\n        for word, count in hashTable.items():\n            if count == 1: res.append(word)\n\n        return res\n```\n---\n# Solution 2 (Trie)\n## Intuition\nThe problem of identifying uncommon words can also be approached using a Trie (prefix tree) data structure. A Trie efficiently stores words and their occurrences as we traverse through each character in the string. This approach may be beneficial when the alphabet is limited, as we can easily navigate through the characters.\n\n## Approach\n1. **Trie Construction:** Use a Trie to store each word. For each character, traverse the Trie structure and mark the end of a word by incrementing a count at the final node.\n2. **Scan the strings:** Process both sentences by inserting words into the Trie and counting how many times each word occurs.\n3. **DFS to retrieve results:** Perform a depth-first search (DFS) on the Trie to find words that appear exactly once. These are the uncommon words.\n4. **Return the result:** Return the list of these uncommon words.\n\n## Complexity\nLet `n` and `m` be the length of string `s1` and `s2` respectively.\n- Time complexity: $$O(n + m)$$.\n    - Traverse string `s1`: $$O(n)$$\n    - Traverse string `s2`: $$O(m)$$\n    - Recursive DFS function algorithm to traverse trie data strcuture: $$O(n + m)$$\n- Space complexity: $$O(n + m)$$\n    - Trie data strcuture: $$O(n + m)$$\n    - Stack of recursive DFS function algorithm to traverse trie data strcuture: $$O(\\max(n, m))$$\n    - Other auxiliary variables: $$O(1)$$\n\n## Code\n```c []\nstruct Trie {\n    uint8_t count;\n    struct Trie *next[26];\n};\n\nstruct Trie* newNode(){\n    struct Trie *new = (struct Trie*)malloc(sizeof(struct Trie));\n\n    new->count = 0;\n    for(int8_t i = 0; i < 26; i++)\n        new->next[i] = NULL;\n\n    return new;\n}\n\nvoid scanString(struct Trie* head, char* s, int *returnSize){\n    struct Trie *ptr = head;\n    uint8_t wordLen = 0, ch;\n\n    for(uint8_t i = 0; s[i]; i++){\n        if(s[i] != \' \'){\n            ch = s[i] - \'a\';\n\n            if(ptr->next[ch] != NULL) ptr = ptr->next[ch];\n            else ptr->next[ch] = newNode(), ptr = ptr->next[ch];\n        }\n        else{\n            if(++ptr->count == 1) (*returnSize)++;\n            else if(ptr->count == 2) (*returnSize)--;\n\n            ptr = head;\n        }\n    }\n\n    if(++ptr->count == 1) (*returnSize)++;\n    else if(ptr->count == 2) (*returnSize)--;\n}\n\nvoid dfsClear(char **res, uint8_t* ind, char* entry, uint8_t i, struct Trie* node){\n    if(node->count == 1){\n        char *word = (char*)malloc(i + 1);\n        word[i] = \'\\0\';\n\n        for(uint8_t j = 0; j < i; j++)\n            word[j] = entry[j];\n\n        res[(*ind)++] = word;\n    }\n\n    for(int8_t j = 0; j < 26; j++)\n        if(node->next[j]){\n            entry[i] = j + \'a\';\n            dfsClear(res, ind, entry, i + 1, node->next[j]);\n        }\n\n    free(node);\n}\n\nchar** uncommonFromSentences(char* s1, char* s2, int* returnSize) {\n    struct Trie *head = newNode();\n    *returnSize = 0;\n\n    scanString(head, s1, returnSize);\n    scanString(head, s2, returnSize);\n\n    char **res = (char**)malloc(sizeof(char*) * (*returnSize));\n\n    char *entry = (char*)malloc(201);\n    dfsClear(res, &(uint8_t*){0}, entry, 0, head);\n\n    free(entry);\n    return res;\n}\n```\n``` cpp []\nclass Solution {\npublic:\n    struct Trie {\n        uint8_t count = 0;\n        struct Trie *next[26] = {nullptr};\n    };\n\n    vector<string> uncommonFromSentences(string s1, string s2) {\n        struct Trie *head = new Trie();\n\n        scanString(head, s1);\n        scanString(head, s2);\n\n        vector<string> res;\n\n        string tmp = "";\n        dfs(res, head, tmp);\n\n        return res;\n    }\n\n    void scanString(struct Trie* head, string& s){\n        struct Trie *ptr = head;\n\n        for(const char& ch : s){\n            if(ch != \' \'){\n                if(ptr->next[ch - \'a\'] == nullptr)\n                    ptr->next[ch - \'a\'] = new Trie();\n                ptr = ptr->next[ch - \'a\'];\n            }\n            else{\n                ptr->count++;\n                ptr = head;\n            }\n        }\n\n        ptr->count++;\n    }\n\n    void dfs(vector<string>& res, struct Trie* node, string& entry){\n        if(node->count == 1)\n            res.push_back(entry);\n\n        for(int8_t i = 0; i < 26; i++){\n            if(node->next[i] != nullptr){\n                entry.push_back(i + \'a\');\n\n                dfs(res, node->next[i], entry);\n\n                entry.pop_back();\n            }\n        }\n    }\n};\n```\n``` java []\nclass Solution {\n    public String[] uncommonFromSentences(String s1, String s2) {\n        Trie head = new Trie();\n\n        short returnSize = 0;\n\n        returnSize += scanString(head, s1);\n        returnSize += scanString(head, s2);\n\n        List<String> res = new ArrayList<String>(returnSize);\n\n        StringBuilder tmp = new StringBuilder("");\n        dfs(res, head, tmp);\n\n        return res.toArray(new String[0]);\n    }\n\n    class Trie {\n        short count;\n        Trie[] next;\n\n        public Trie() {\n            this.count = 0;\n            this.next = new Trie[26];\n            for(byte i = 0; i < 26; i++)\n                this.next[i] = null;\n        }\n    }\n\n    short scanString(Trie head, String s){\n        Trie ptr = head;\n        short count, returnSize = 0;\n\n        for(short i = 0, n = (short) s.length(); i < n; i++){\n            if(s.charAt(i) != \' \'){\n                if(ptr.next[s.charAt(i) - \'a\'] == null)\n                    ptr.next[s.charAt(i) - \'a\'] = new Trie();\n                ptr = ptr.next[s.charAt(i) - \'a\'];\n            }\n            else{\n                if(ptr.count == 0) returnSize++;\n                else if(ptr.count == 1) returnSize--;\n\n                ptr.count++;\n                ptr = head;\n            }\n        }\n\n        if(ptr.count == 0) returnSize++;\n        else if(ptr.count == 1) returnSize--;\n\n        ptr.count++;\n        return returnSize;\n    }\n\n    void dfs(List<String> res, Trie node, StringBuilder entry){\n        if(node != null && node.count == 1)\n            res.add(entry.toString());\n\n        for(byte i = 0; i < 26; i++){\n            if(node != null && node.next[i] != null){\n                entry.append((char) (i + \'a\'));\n\n                dfs(res, node.next[i], entry);\n\n                entry.setLength(entry.length() - 1);\n            }\n        }\n    }\n}\n```\n``` python3 []\nclass Solution:\n    def uncommonFromSentences(self, s1: str, s2: str) -> List[str]:\n        class Trie:\n            def __init__(self):\n                self.count = 0\n                self.next = [None] * 26\n            \n        def scanString(head, s):\n            ptr = head\n\n            for ch in s:\n                if ch != \' \':\n                    if ptr.next[ord(ch) - ord(\'a\')] is None:\n                        ptr.next[ord(ch) - ord(\'a\')] = Trie()\n                    ptr = ptr.next[ord(ch) - ord(\'a\')]\n                else:\n                    ptr.count += 1\n                    ptr = head\n\n            ptr.count += 1\n\n        def dfs(res, node, entry):\n            if node.count == 1:\n                res.append(entry)\n\n            for i in range(26):\n                if node.next[i] is not None:\n                    entry += chr(97 + i)\n\n                    dfs(res, node.next[i], entry)\n\n                    entry = entry[0 : len(entry) - 1]\n                \n        head = Trie()\n        \n        scanString(head, s1)\n        scanString(head, s2)\n\n        res = []\n\n        dfs(res, head, "")\n\n        return res\n```
['Hash Table', 'String', 'Tree', 'C', 'Counting', 'C++', 'Java', 'Python3']