Dialogue Similarity - codepath/compsci_guides GitHub Wiki

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q
  • What is the desired outcome?
    • To determine if two sentences are similar based on given pairs of similar words.
  • What input is provided?
    • Two string arrays sentence1 and sentence2, and an array of string pairs similar_pairs.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Build a similarity map from similar_pairs and compare corresponding words in sentence1 and sentence2.

1) Check if `sentence1` and `sentence2` have the same length. If not, return `False`.
2) Build a similarity map using a dictionary of sets.
3) Compare corresponding words in `sentence1` and `sentence2`.
   - If the words are equal, continue.
   - If the words are different, check if they are in the similarity map.
   - If they are not similar, return `False`.
4) If all words are similar, return `True`.

⚠️ Common Mistakes

• Not handling the case where sentence1 and sentence2 are of different lengths.

I-mplement

def is_similar(sentence1, sentence2, similar_pairs):
    # Step 1: Check if both sentences have the same length
    if len(sentence1) != len(sentence2):
        return False
    
    # Step 2: Build the similarity map
    similarity_map = {}
    for pair in similar_pairs:
        if pair[0] not in similarity_map:
            similarity_map[pair[0]] = set()
        if pair[1] not in similarity_map:
            similarity_map[pair[1]] = set()
        similarity_map[pair[0]].add(pair[1])
        similarity_map[pair[1]].add(pair[0])
    
    # Step 3: Compare corresponding words
    for word1, word2 in zip(sentence1, sentence2):
        if word1 == word2:
            continue
        if word1 in similarity_map and word2 in similarity_map[word1]:
            continue
        if word2 in similarity_map and word1 in similarity_map[word2]:
            continue
        return False
    
    return True