Similar string | Challenge | Code approach

Question

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.

Answer 1

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).

Answer 2

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.