Similar string | Challenge | Code approach | Sololearn: Learn to code for FREE!

+2

Similar string | Challenge | Code approach

Hi Please refer below code: It has comment to describe problem statement and example input. https://code.sololearn.com/ca177A400a18 Is my code proper in terms of time complexity? I thought to use unordered_multimap but as I need to find element based on value as well from map, it would be again O(n) so discarded that idea. Feel free to share your view.

5/16/2021 11:07:24 AM

Ketan Lalcheta

2 Answers

New Answer

+7

My basic brute force approach will be to make connected components (graph) using vector<vector<string>> simillar_words, and then for every word in sentence1 I will search for corresponding word of sentence2 in connected component of word of sentence1 using bfs or dfs. It is O(n^2) approach, maybe something similar you are doing ? //maybe disjoint set union(DSU) can help here to reduce complexity to O(nlogn).

+3

easy O(n) approach possible: You can use unordered_map<string, int> component_no; for storing which word belongs to which component, you can mark component as 1,2,... . First construct the graph and then run dfs from every unvisited word and mark all connected words to it as same comp no. . void dfs(string u, int comp){ vis[u]=true; component_no[u]=comp; for(string v:graph[u]) if(!vis[v]) dfs(v,comp); } int main(){ int comp=1; for(string str:sentence1) if(!vis[str]){ dfs(str, comp); comp++; } for(string str:sentence2) if(!vis[str]){ dfs(str, comp); comp++; } return 0; } Then for checking if any 2 words belonging to same component is just O(1) operation.