737. Sentence Similarity II

LeetCode medium оригинал: C# #array #csharp #graph #hash-table #leetcode #medium #search #string

LeetCode Static

Мы можем представить предложение в виде массива слов, например, предложение "I am happy with leetcode" можно представить как arr = ["I", "am",happy", "with", "leetcode"].

Даны два предложения sentence1 и sentence2, каждое из которых представлено в виде массива строк, и массив пар строк similarPairs, где similarPairs[i] = [xi, yi] указывает, что два слова xi и yi похожи. Возвращается true, если предложения sentence1 и sentence2 похожи, или false, если они не похожи. Два предложения похожи, если: у них одинаковая длина (т.е, Заметьте, что слово всегда похоже само на себя, также обратите внимание, что отношение сходства является транзитивным. Например, если слова a и b похожи, а слова b и c похожи, то a и c похожи.

Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","good"],["fine","good"],["drama","acting"],["skills","talent"]]

Output: true

C# решение

сопоставлено/оригинал

using System;
using System.Collections.Generic;
public class Solution {
    public bool AreSentencesSimilar(string[] sentence1, string[] sentence2, IList<IList<string>> similarPairs) {
        if (sentence1.Length != sentence2.Length) {
            return false;
        }
        var graph = new Dictionary<string, List<string>>();
        foreach (var pair in similarPairs) {
            if (!graph.ContainsKey(pair[0])) graph[pair[0]] = new List<string>();
            if (!graph.ContainsKey(pair[1])) graph[pair[1]] = new List<string>();
            graph[pair[0]].Add(pair[1]);
            graph[pair[1]].Add(pair[0]);
        }
        for (int i = 0; i < sentence1.Length; i++) {
            if (sentence1[i] != sentence2[i] && !dfs(sentence1[i], sentence2[i], graph, new HashSet<string>())) {
                return false;
            }
        }
        return true;
    }
    private bool dfs(string word1, string word2, Dictionary<string, List<string>> graph, HashSet<string> visited) {
        if (word1 == word2) {
            return true;
        }
        visited.Add(word1);
        foreach (var neighbor in graph.GetValueOrDefault(word1, new List<string>())) {
            if (!visited.Contains(neighbor) && dfs(neighbor, word2, graph, visited)) {
                return true;
            }
        }
        return false;
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool AreSentencesSimilar(vector<string> sentence1, vector<string> sentence2, IList<vector<string>> similarPairs) {
        if (sentence1.size() != sentence2.size()) {
            return false;
        }
        var graph = new unordered_map<string, List<string>>();
        foreach (var pair in similarPairs) {
            if (!graph.count(pair[0])) graph[pair[0]] = new List<string>();
            if (!graph.count(pair[1])) graph[pair[1]] = new List<string>();
            graph[pair[0]].push_back(pair[1]);
            graph[pair[1]].push_back(pair[0]);
        }
        for (int i = 0; i < sentence1.size(); i++) {
            if (sentence1[i] != sentence2[i] && !dfs(sentence1[i], sentence2[i], graph, new HashSet<string>())) {
                return false;
            }
        }
        return true;
    }
    private bool dfs(string word1, string word2, unordered_map<string, List<string>> graph, HashSet<string> visited) {
        if (word1 == word2) {
            return true;
        }
        visited.push_back(word1);
        foreach (var neighbor in graph.GetValueOrDefault(word1, new List<string>())) {
            if (!visited.Contains(neighbor) && dfs(neighbor, word2, graph, visited)) {
                return true;
            }
        }
        return false;
    }
}

Java решение

сопоставлено/оригинал

import java.util.*;

public class Solution {
    public boolean areSentencesSimilar(String[] sentence1, String[] sentence2, List<List<String>> similarPairs) {
        if (sentence1.length != sentence2.length) {
            return false;
        }
        
        Map<String, List<String>> graph = new HashMap<>();
        for (List<String> pair : similarPairs) {
            graph.computeIfAbsent(pair.get(0), k -> new ArrayList<>()).add(pair.get(1));
            graph.computeIfAbsent(pair.get(1), k -> new ArrayList<>()).add(pair.get(0));
        }
        
        for (int i = 0; i < sentence1.length; i++) {
            if (!sentence1[i].equals(sentence2[i]) && !dfs(sentence1[i], sentence2[i], graph, new HashSet<>())) {
                return false;
            }
        }
        
        return true;
    }
    
    private boolean dfs(String word1, String word2, Map<String, List<String>> graph, Set<String> visited) {
        if (word1.equals(word2)) {
            return true;
        }
        visited.add(word1);
        for (String neighbor : graph.getOrDefault(word1, Collections.emptyList())) {
            if (!visited.contains(neighbor) && dfs(neighbor, word2, graph, visited)) {
                return true;
            }
        }
        return false;
    }
}

JavaScript решение

сопоставлено/оригинал

var areSentencesSimilar = function(sentence1, sentence2, similarPairs) {
    if (sentence1.length !== sentence2.length) {
        return false;
    }

    const graph = {};
    for (const [x, y] of similarPairs) {
        if (!graph[x]) graph[x] = [];
        if (!graph[y]) graph[y] = [];
        graph[x].push(y);
        graph[y].push(x);
    }

    const dfs = (word1, word2, visited) => {
        if (word1 === word2) return true;
        visited.add(word1);
        for (const neighbor of graph[word1] || []) {
            if (!visited.has(neighbor) && dfs(neighbor, word2, visited)) {
                return true;
            }
        }
        return false;
    };

    for (let i = 0; i < sentence1.length; i++) {
        const w1 = sentence1[i], w2 = sentence2[i];
        if (w1 !== w2) {
            if (!dfs(w1, w2, new Set())) {
                return false;
            }
        }
    }

    return true;
};

Python решение

сопоставлено/оригинал

def areSentencesSimilar(sentence1, sentence2, similarPairs):
    if len(sentence1) != len(sentence2):
        return False
    
    graph = {}
    for x, y in similarPairs:
        if x not in graph:
            graph[x] = []
        if y not in graph:
            graph[y] = []
        graph[x].append(y)
        graph[y].append(x)
    
    def dfs(word1, word2, visited):
        if word1 == word2:
            return True
        visited.add(word1)
        for neighbor in graph.get(word1, []):
            if neighbor not in visited and dfs(neighbor, word2, visited):
                return True
        return False
    
    for w1, w2 in zip(sentence1, sentence2):
        if w1 != w2 and not dfs(w1, w2, set()):
            return False
    
    return True

Go решение

сопоставлено/оригинал

package main

func areSentencesSimilar(sentence1 []string, sentence2 []string, similarPairs [][]string) bool {
    if len(sentence1) != len(sentence2) {
        return false
    }

    graph := make(map[string][]string)
    for _, pair := range similarPairs {
        x, y := pair[0], pair[1]
        graph[x] = append(graph[x], y)
        graph[y] = append(graph[y], x)
    }

    var dfs func(word1, word2 string, visited map[string]bool) bool
    dfs = func(word1, word2 string, visited map[string]bool) bool {
        if word1 == word2 {
            return true
        }
        visited[word1] = true
        for _, neighbor := range graph[word1] {
            if !visited[neighbor] && dfs(neighbor, word2, visited) {
                return true
            }
        }
        return false
    }

    for i := range sentence1 {
        if sentence1[i] != sentence2[i] {
            visited := make(map[string]bool)
            if !dfs(sentence1[i], sentence2[i], visited) {
                return false
            }
        }
    }

    return true
}

Algorithm

Проверить, одинаковой ли длины предложения sentence1 и sentence2. Если нет, вернуть false.

Построить граф схожести слов с использованием словаря.

Использовать поиск в глубину (DFS) для проверки транзитивной схожести слов в предложениях.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.