Sentence Similarity

šŸ  ā¬…ļø āž”ļø

We can represent a sentence as an array of words, for example, the sentence "I am happy with leetcode " can be represented as arr = [ "I ", "am ",happy ", "with ", "leetcode "].

Given two sentences sentence1 and sentence2 each represented as a string array and given an array of string pairs similarPairs where similarPairs[i] = [xi, yi] indicates that the two words xi and yi are similar.

Return true if sentence1 and sentence2 are similar, or false if they are not similar.

Two sentences are similar if:

  • They have the same length (i.e., the same number of words)
  • sentence1[i] and sentence2[i] are similar.

Notice that a word is always similar to itself, also notice that the similarity relation is not transitive. For example, if the words a and b are similar, and the words b and c are similar, a and c are not necessarily similar.

Example 1:

Input: sentence1 = [ "great ", "acting ", "skills "], sentence2 = [ "fine ", "drama ", "talent "], similarPairs = [[ "great ", "fine "],[ "drama ", "acting "],[ "skills ", "talent "]] Output: true Explanation: The two sentences have the same length and each word i of sentence1 is also similar to the corresponding word in sentence2.

Example 2:

Input: sentence1 = [ "great "], sentence2 = [ "great "], similarPairs = [] Output: true Explanation: A word is similar to itself.

Example 3:

Input: sentence1 = [ "great "], sentence2 = [ "doubleplus ", "good "], similarPairs = [[ "great ", "doubleplus "]] Output: false Explanation: As they don't have the same length, we return false.

Constraints:

  • 1 <= sentence1.length, sentence2.length <= 1000
  • 1 <= sentence1[i].length, sentence2[i].length <= 20
  • sentence1[i] and sentence2[i] consist of English letters.
  • 0 <= similarPairs.length <= 1000
  • similarPairs[i].length == 2
  • 1 <= xi.length, yi.length <= 20
  • xi and yi consist of lower-case and upper-case English letters.
  • All the pairs (xi, yi) are distinct.
Note: This problem is from LeetCode.
āŒ Compiled
āŒ Executed
āŒ Correct 
program main
    implicit none

    integer :: i, j, n, m
    character(len=20), allocatable :: arr(:)
    character(len=20), allocatable :: sentence1(:), sentence2(:)
    character(len=20), allocatable :: xi(:), yi(:)
    logical :: result

    ! Examples
    n = 5
    allocate(arr(n))
    arr = ["I ", "am ", "happy ", "with ", "leetcode "]
    call print_array(arr)

    n = 4
    allocate(sentence1(n))
    sentence1 = ["great ", "acting ", "skills "]
    allocate(sentence2(n))
    sentence2 = ["fine ", "drama ", "talent "]
    allocate(xi(2))
    allocate(yi(2))
    xi = ["great ", "drama "]
    yi = ["fine ", "acting "]
    result = are_sentences_similar(sentence1, sentence2, xi, yi)
    write (*, '(A, L1)') "Example 1:", result

    n = 1
    allocate(sentence1(n))
    sentence1 = ["great "]
    allocate(sentence2(n))
    sentence2 = ["great "]
    allocate(xi(0))
    allocate(yi(0))
    result = are_sentences_similar(sentence1, sentence2, xi, yi)
    write (*, '(A, L1)') "Example 2:", result

    n = 1
    allocate(sentence1(n))
    sentence1 = ["great "]
    allocate(sentence2(n))
    sentence2 = ["doubleplus ", "good "]
    allocate(xi(1))
    allocate(yi(1))
    xi = ["great "]
    yi = ["doubleplus "]
    result = are_sentences_similar(sentence1, sentence2, xi, yi)
    write (*, '(A, L1)') "Example 3:", result

contains

    subroutine print_array(arr)
        implicit none
        character(len=20), intent(in) :: arr(:)
        do i = 1, size(arr)
            write (*, '(A)', advance='no') trim(arr(i)) // " "
        end do
        write (*, *) ""
    end subroutine print_array

end program main

function are_sentences_similar(sentence1, sentence2, similarPairs) result(result)
    implicit none
    character(len=20), intent(in) :: sentence1(:), sentence2(:)
    character(len=20), intent(in) :: similarPairs(:, :)
    logical :: result
    integer :: i, j, k, l

    ! Check if both sentences have the same length
    if (size(sentence1) /= size(sentence2)) then
        result = .false.
        return
    end if

    ! Check if each word in sentence1 is similar to the corresponding word in sentence2
    do i = 1, size(sentence1)
        do j = 1, size(similarPairs, dim=1)
            if (sentence1(i) == similarPairs(j, 1) .and. &
                sentence2(i) == similarPairs(j, 2)) then
                exit
            end if
        end do
        if (j > size(similarPairs, dim=1)) then
            result = .false.
            return
        end if
    end do

    result = .true.

end function are_sentences_similar
āŒ Compiled
āŒ Executed
āŒ Correct 
module is_similar_sentence

contains

  function is_similar_sentence(sentence1, sentence2, similar_pairs) result(is_similar)
    implicit none
    character(len=*), intent(in) :: sentence1(:), sentence2(:)
    character(len=*), intent(in) :: similar_pairs(:, :)
    logical :: is_similar
    integer :: i, j, k

    ! Check if the sentences have the same length
    if (size(sentence1) /= size(sentence2)) then
      is_similar = .false.
      return
    end if

    ! Check if each word in sentence1 is similar to the corresponding word in sentence2
    do i = 1, size(sentence1)
      do j = 1, size(similar_pairs, 1)
        if (sentence1(i) == similar_pairs(j, 1) .and. sentence2(i) == similar_pairs(j, 2)) then
          exit
        end if
      end do
      if (j > size(similar_pairs, 1)) then
        is_similar = .false.
        return
      end if
    end do

    ! If we reach this point, the sentences are similar
    is_similar = .true.

  end function is_similar_sentence

end module is_similar_sentence

program test_is_similar_sentence
  use is_similar_sentence
  implicit none
  character(len=*), parameter :: sentence1(3) = ["I ", "am ", "happy "]
  character(len=*), parameter :: sentence2(3) = ["I ", "am ", "happy "]
  character(len=*), parameter :: similar_pairs(2, 2) = reshape([character(len=20) :: "I ", "am ", "happy ", "I ", "am ", "happy "], shape(similar_pairs))
  logical :: is_similar

  is_similar = is_similar_sentence(sentence1, sentence2, similar_pairs)
  if (is_similar) then
    print *, "The sentences are similar."
  else
    print *, "The sentences are not similar."
  end if

  ! Test case 2:
  character(len=*), parameter :: sentence3(2) = ["I ", "am "]
  character(len=*), parameter :: sentence4(3) = ["I ", "am ", "happy "]
  character(len=*), parameter :: similar_pairs2(1, 2) = reshape([character(len=20) :: "I ", "am "], shape(similar_pairs2))

  is_similar = is_similar_sentence(sentence3, sentence4, similar_pairs2)
  if (is_similar) then
    print *, "The sentences are similar."
  else
    print *, "The sentences are not similar."
  end if

  ! Test case 3:
  character(len=*), parameter :: sentence5(2) = ["I ", "am "]
  character(len=*), parameter :: sentence6(2) = ["I ", "am "]
  character(len=*), parameter :: similar_pairs3(0, 2) = reshape([character(len=20) ::], shape(similar_pairs3))

  is_similar = is_similar_sentence(sentence5, sentence6, similar_pairs3)
  if (is_similar) then
    print *, "The sentences are similar."
  else
    print *, "The sentences are not similar."
  end if

end program test_is_similar_sentence
šŸŒ Data from online sources 
from collections import defaultdict

def areSentencesSimilar(sentence1, sentence2, similarPairs):
    if len(sentence1) != len(sentence2): return False
    similarityMap = defaultdict(set)
    for pair in similarPairs:
        similarityMap[pair[0]].add(pair[1])
        similarityMap[pair[1]].add(pair[0])
    for i in range(len(sentence1)):
        if sentence1[i] != sentence2[i] and sentence2[i] not in similarityMap[sentence1[i]]:
            return False
    return True

1. If the lengths of the given sentences are unequal, the sentences cannot be similar, hence return false.
  1. Create a mapping from each word in similarPairs to its set of similar words.
  2. Iterate over each word in both sentences and check whether they are similar. If not, return false.
  3. If all words in sentence1 are similar to words at same indices in sentence2, return true.
šŸŒ Data from online sources 
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

bool areSentencesSimilar(vector<string>& sentence1, vector<string>& sentence2, vector<vector<string>>& similarPairs) {
    if (sentence1.size() != sentence2.size()) return false;
    unordered_map<string, unordered_set<string>> similarityMap;
    for (const auto& pair : similarPairs) {
        similarityMap[pair[0]].insert(pair[1]);
        similarityMap[pair[1]].insert(pair[0]);
    }
    for (int i = 0; i < sentence1.size(); ++i) {
        if (sentence1[i] != sentence2[i] && !similarityMap[sentence1[i]].count(sentence2[i]))
            return false;
    }
    return true;
}

1. If the lengths of the given sentences are unequal, the sentences cannot be similar, hence return false.
  1. Create a mapping from each word in similarPairs to its set of similar words.
  2. Iterate over each word in both sentences and check whether they are similar. If not, return false.
  3. If all words in sentence1 are similar to words at same indices in sentence2, return true.