اکنون در دسترس! پژوهش تلگرام ۲۰۲۵ — مهمترین بینشهای سال 
Java | LeetCode
رفتن به کانال در Telegram
Cайт easyoffer.ru Реклама @easyoffer_adv ВП @easyoffer_vp Тесты t.me/+icUwivvbGOkwNWRi Вопросы собесов t.me/+7ESm0VKXC4tjYzky Вакансии t.me/+4pspF5nDjgM4MjQy
نمایش بیشتر6 657
مشترکین
-424 ساعت
-197 روز
-4930 روز
آرشیو پست ها
6 658
Задача: 1461. Check If a String Contains All Binary Codes of Size K
Сложность: medium
Дана бинарная строка s и целое число k, верните true, если каждый бинарный код длины k является подстрокой s. В противном случае верните false.
Пример:
Input: s = "00110110", k = 2 Output: true Explanation: The binary codes of length 2 are "00", "01", "10" and "11". They can be all found as substrings at indices 0, 1, 3 and 2 respectively.👨💻 Алгоритм: 1⃣Определите количество возможных двоичных кодов длины k. 2⃣Создайте массив для отслеживания, какие коды были найдены. Итерируйте по строке s, вычисляя хэш для текущего окна длины k и обновляя массив отслеживания. 3⃣Возвращайте true, если все возможные коды найдены, иначе false. 😎 Решение:
class Solution {
public static boolean hasAllCodes(String s, int k) {
int need = 1 << k;
boolean[] got = new boolean[need];
int allOne = need - 1;
int hashVal = 0;
for (int i = 0; i < s.length(); i++) {
hashVal = ((hashVal << 1) & allOne) | (s.charAt(i) - '0');
if (i >= k - 1 && !got[hashVal]) {
got[hashVal] = true;
need--;
if (need == 0) {
return true;
}
}
}
return false;
}
}6 658
Вакансия удалённый 1C-программист. З/П до 250 000 ₽
Ищем 1С-программиста с опытом от 3-х лет на full-time. Аккредитованная IT-компания. Удалённая работа из любой точки мира. ДМО. Оформление в штат по ТК РФ. Зарплата до 250000 ₽. Помощь в развитии.
Стань частью профессиональной команды Programming Store. Переходи по ссылке и откликайся!
Подать заявку
#реклама
mrqz.me
О рекламодателе
6 658
Задача: 914. X of a Kind in a Deck of Cards
Сложность: easy
Вам дан целочисленный массив deck, где deck[i] - число, написанное на i-й карте. Разделите карты на одну или несколько групп так, чтобы: в каждой группе было ровно x карт, где x > 1, и на всех картах в одной группе было написано одно и то же целое число. Верните true, если такое разделение возможно, или false в противном случае.
Пример:
Input: deck = [1,2,3,4,4,3,2,1] Output: true👨💻 Алгоритм: 1⃣Создать словарь для подсчета частоты каждого числа в массиве deck. 2⃣Найти наибольший общий делитель (НОД) всех частот. 3⃣Проверить, больше ли НОД 1, чтобы определить, можно ли разделить карты на группы. 😎 Решение:
import java.util.*;
import java.util.stream.Collectors;
class Solution {
public boolean hasGroupsSizeX(int[] deck) {
Map<Integer, Integer> count = new HashMap<>();
for (int num : deck) {
count.put(num, count.getOrDefault(num, 0) + 1);
}
int g = count.values().stream().reduce(this::gcd).orElse(0);
return g > 1;
}
private int gcd(int a, int b) {
while (b != 0) {
int temp = a % b;
a = b;
b = temp;
}
return a;
}
}6 658
Задача: 1037. Valid Boomerang
Сложность: easy
Если задан массив points, где points[i] = [xi, yi] представляет точку на плоскости X-Y, верните true, если эти точки являются бумерангом. Бумеранг - это набор из трех точек, которые отличаются друг от друга и не являются прямой линией.
Пример:
Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2] Output: false👨💻 Алгоритм: 1⃣Проверка уникальности точек: Убедитесь, что все три точки уникальны. Если любые две точки совпадают, то это не бумеранг. 2⃣Проверка на коллинеарность: Используйте определитель (или площадь параллелограмма) для проверки, находятся ли три точки на одной прямой. Если площадь параллелограмма, образованного тремя точками, равна нулю, то точки коллинеарны. 3⃣Результат: Если точки уникальны и не коллинеарны, верните true. В противном случае, верните false. 😎 Решение:
var isBoomerang = function(points) {
let [x1, y1] = points[0];
let [x2, y2] = points[1];
let [x3, y3] = points[2];
return (x1 !== x2 || y1 !== y2) &&
(x1 !== x3 || y1 !== y3) &&
(x2 !== x3 || y2 !== y3) &&
(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) !== 0;
};6 658
Дарим подписку на Яндекс Музыку
Ответьте на 1 вопрос и Яндекс Музыка ваша для вас и 3-х ваших близких.
Кинопоиск и Яндекс Книги тоже в подписке.
Попробуйте бесплатно❤️
Попробовать
#реклама 18+
music.yandex.ru
О рекламодателе
Реклама на Яндексе
6 658
Задача: 685. Redundant Connection II
Сложность: hard
В этой задаче корневое дерево — это направленный граф, в котором существует ровно один узел (корень), для которого все остальные узлы являются потомками этого узла, плюс каждый узел имеет ровно одного родителя, за исключением корневого узла, у которого нет родителей.
Данный ввод представляет собой направленный граф, который изначально был корневым деревом с n узлами (со значениями от 1 до n), и к которому добавлено одно дополнительное направленное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее.
Результирующий граф представлен в виде двумерного массива ребер. Каждый элемент массива edges — это пара [ui, vi], представляющая направленное ребро, соединяющее узлы ui и vi, где ui является родителем ребенка vi.
Верните ребро, которое можно удалить, чтобы результирующий граф стал корневым деревом с n узлами. Если существует несколько ответов, верните ответ, который встречается последним в данном двумерном массиве.
Пример:
Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]class Solution {
public int[] findRedundantDirectedConnection(int[][] edges) {
int N = edges.length;
Map<Integer, Integer> parent = new HashMap<>();
List<int[]> candidates = new ArrayList<>();
for (int[] edge : edges) {
if (parent.containsKey(edge[1])) {
candidates.add(new int[]{parent.get(edge[1]), edge[1]});
candidates.add(edge);
} else {
parent.put(edge[1], edge[0]);
}
}
int root = orbit(1, parent).node;
if (candidates.isEmpty()) {
Set<Integer> cycle = orbit(root, parent).seen;
for (int[] edge : edges) {
if (cycle.contains(edge[0]) && cycle.contains(edge[1])) {
return edge;
}
}
}
Map<Integer, List<Integer>> children = new HashMap<>();
for (int v : parent.keySet()) {
int pv = parent.get(v);
children.computeIfAbsent(pv, k -> new ArrayList<>()).add(v);
}
boolean[] seen = new boolean[N + 1];
Stack<Integer> stack = new Stack<>();
stack.add(root);
while (!stack.isEmpty()) {
int node = stack.pop();
if (!seen[node]) {
seen[node] = true;
if (children.containsKey(node)) {
stack.addAll(children.get(node));
}
}
}
for (boolean b : seen) {
if (!b) {
return candidates.get(0);
}
}
return candidates.get(1);
}
public OrbitResult orbit(int node, Map<Integer, Integer> parent) {
Set<Integer> seen = new HashSet<>();
while (parent.containsKey(node) && !seen.contains(node)) {
seen.add(node);
node = parent.get(node);
}
return new OrbitResult(node, seen);
}
}
class OrbitResult {
int node;
Set<Integer> seen;
OrbitResult(int n, Set<Integer> s) {
node = n;
seen = s;
}
}6 658
📺 Уникальная база IT собеседований
456+ реальных собеседований на программиста, тестировщика, аналитика и прочие IT профы.
Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д.
🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!
6 658
Задача: 338. Counting Bits
Сложность: easy
Дано целое число n, верните массив ans длиной n + 1, такой что для каждого i (0 <= i <= n), ans[i] будет равняться количеству единиц в двоичном представлении числа i.
Пример:
Input: n = 5 Output: [0,1,1,2,1,2] Explanation: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101👨💻 Алгоритм: 1⃣ Инициализация массива: Создайте массив ans длиной n + 1, заполненный нулями. Этот массив будет содержать количество единиц в двоичном представлении каждого числа от 0 до n. 2⃣ Итерация и вычисление: Пройдите в цикле по всем числам от 1 до n. Для каждого числа x используйте битовую операцию x & (x - 1), чтобы убрать последнюю установленную биту, и добавьте 1 к значению ans для этого результата. Это количество единиц в двоичном представлении числа x. 3⃣ Возврат результата: Верните заполненный массив ans, который содержит количество единиц для каждого числа от 0 до n. 😎 Решение:
public class Solution {
public int[] countBits(int num) {
int[] ans = new int[num + 1];
for (int x = 1; x <= num; ++x) {
ans[x] = ans[x & (x - 1)] + 1;
}
return ans;
}
}6 658
Задача: 1061. Lexicographically Smallest Equivalent String
Сложность: medium
Даны две строки одинаковой длины s1 и s2, а также строка baseStr.
Мы говорим, что символы s1[i] и s2[i] эквивалентны.
Например, если s1 = "abc" и s2 = "cde", то 'a' == 'c', 'b' == 'd' и 'c' == 'e'. Эквивалентные символы следуют правилам рефлексивности, симметрии и транзитивности.
Верните лексикографически наименьшую эквивалентную строку baseStr, используя информацию об эквивалентности из s1 и s2.
Пример:
Input: s1 = "parker", s2 = "morris", baseStr = "parser"
Output: "makkek"
Explanation: Based on the equivalency information in s1 and s2, we can group their characters as [m,p], [a,o], [k,r,s], [e,i].
The characters in each group are equivalent and sorted in lexicographical order.
So the answer is "makkek".class Solution {
int minChar;
void DFS(int src, Integer[][] adjMatrix, Integer visited[], List<Integer> component) {
// Mark the character as visited.
visited[src] = 1;
// Add it to the list.
component.add(src);
// Update the minimum character in the component.
minChar = Math.min(minChar, src);
for (int i = 0; i < 26; i++) {
// Perform DFS if the edge exists and the node isn't visited yet.
if (adjMatrix[src][i] != null && visited[i] == null) {
DFS(i, adjMatrix, visited, component);
}
}
}
public String smallestEquivalentString(String s1, String s2, String baseStr) {
// Adjacency matrix to store edges.
Integer adjMatrix[][] = new Integer[26][26];
for (int i = 0; i < s1.length(); i++) {
adjMatrix[s1.charAt(i) - 'a'][s2.charAt(i) - 'a'] = 1;
adjMatrix[s2.charAt(i) - 'a'][s1.charAt(i) - 'a'] = 1;
}
// Array to store the final character mappings.
int mappingChar[] = new int[26];
for (int i = 0; i < 26; i++) {
mappingChar[i] = i;
}
// Array to keep visited nodes during DFS.
Integer visited[] = new Integer[26];
for (int c = 0; c < 26; c++) {
if (visited[c] == null) {
// Store the characters in the current component.
List<Integer> component = new ArrayList<>();
// Variable to store the minimum character in the component.
minChar = 27;
DFS(c, adjMatrix, visited, component);
// Map the characters in the component to the minimum character.
for (int vertex : component) {
mappingChar[vertex] = minChar;
}
}
}
String ans = "";
// Create the answer string.
for (char c : baseStr.toCharArray()) {
ans += (char)(mappingChar[c - 'a'] + 'a');
}
return ans;
}
}6 658
Задача: 293. Flip Game
Сложность: easy
Вы играете в игру Flip со своим другом.
Вам дана строка currentState, которая содержит только символы '+' и '-'. Вы и ваш друг по очереди переворачиваете две последовательные "++" в "--". Игра заканчивается, когда один из игроков больше не может сделать ход, и, следовательно, другой игрок становится победителем.
Верните все возможные состояния строки currentState после одного допустимого хода. Вы можете вернуть ответы в любом порядке. Если допустимых ходов нет, верните пустой список [].
Пример:
Input: currentState = "++++" Output: ["--++","+--+","++--"]👨💻 Алгоритм: 1⃣Создайте пустой массив nextPossibleStates для хранения всех возможных следующих состояний после одного хода. 2⃣Запустите цикл от index = 0 до currentState.size() - 1. Для каждого индекса: Если символы на позициях index и index + 1 равны '+': Создайте новую строку nextState, заменив две последовательные '+' на '--'. Используйте конкатенацию строк для создания nextState из подстроки до первого '+', "--" и подстроки после второго '+' до конца. Сохраните созданное nextState в массив nextPossibleStates. 3⃣После цикла верните массив nextPossibleStates, содержащий все возможные следующие состояния. 😎 Решение:
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<String> generatePossibleNextMoves(String currentState) {
List<String> nextPossibleStates = new ArrayList<>();
for (int index = 0; index < currentState.length() - 1; index++) {
if (currentState.charAt(index) == '+' && currentState.charAt(index + 1) == '+') {
String nextState = currentState.substring(0, index) + "--" + currentState.substring(index + 2);
nextPossibleStates.add(nextState);
}
}
return nextPossibleStates;
}
}6 658
Крупнейший университет искусственного интеллекта
Приглашаем на бесплатный курс по искусственному интеллекту!
Мы подготовили для тебя 5 занятий по теме «Разработка нейро-сотрудников на GPT». Пройди регистрацию для получения полного бесплатного доступа к курсу.
✨ 8 000+ студентов со всего мира
✨ 600+ AI-проектов, созданных студентами
✨ Сборная Университета — победители крупнейших AI-хакатонов России
✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие)
✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие)
Будем рады видеть тебя в наших рядах!
Узнать больше
#реклама 16+
neural-university.ru
О рекламодателе
6 658
Задача: 1087. Brace Expansion
Сложность: medium
Дан список оценок различных студентов, items, где items[i] = [IDi, scorei] представляет собой одну оценку студента с идентификатором IDi. Вычислите среднее значение пяти лучших оценок каждого студента.
Верните ответ в виде массива пар result, где result[j] = [IDj, topFiveAveragej] представляет студента с идентификатором IDj и его среднее значение пяти лучших оценок. Отсортируйте result по IDj в порядке возрастания.
Среднее значение пяти лучших оценок студента вычисляется путем сложения его пяти лучших оценок и деления на 5 с использованием целочисленного деления.
Пример:
Input: s = "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]class Solution {
private int storeFirstOptions(String s, int startPos, List<Character> firstOptions) {
if (s.charAt(startPos) != '{') {
firstOptions.add(s.charAt(startPos));
} else {
startPos++;
while (s.charAt(startPos) != '}') {
if (Character.isLowerCase(s.charAt(startPos))) {
firstOptions.add(s.charAt(startPos));
}
startPos++;
}
Collections.sort(firstOptions);
}
return startPos + 1;
}
private List<String> findAllWords(String s, int startPos) {
if (startPos == s.length()) {
return Arrays.asList("");
}
List<Character> firstOptions = new ArrayList<>();
int remStringStartPos = storeFirstOptions(s, startPos, firstOptions);
List<String> wordsWithRemString = findAllWords(s, remStringStartPos);
List<String> expandedWords = new ArrayList<>();
for (char c : firstOptions) {
for (String word : wordsWithRemString) {
expandedWords.add(c + word);
}
}
return expandedWords;
}
public List<String> expand(String s) {
return findAllWords(s, 0);
}
}6 658
Задача: 661. Image Smoother
Сложность: easy
Дан целочисленный матрица img размером m x n, представляющая градации серого изображения. Верните изображение после применения сглаживания к каждой его ячейке.
Пример:
Input: img = [[1,1,1],[1,0,1],[1,1,1]] Output: [[0,0,0],[0,0,0],[0,0,0]] Explanation: For the points (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0 For the points (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0 For the point (1,1): floor(8/9) = floor(0.88888889) = 0👨💻 Алгоритм: 1⃣Инициализация: Создайте новую матрицу такого же размера, чтобы сохранить результат сглаживания. 2⃣Обработка каждой ячейки: Для каждой ячейки исходной матрицы найдите всех её соседей (включая саму ячейку). Вычислите среднее значение этих ячеек и сохраните его в соответствующей ячейке результирующей матрицы. 3⃣Возврат результата: Верните результирующую матрицу после применения сглаживания ко всем ячейкам. 😎 Решение:
public class Solution {
public int[][] imageSmoother(int[][] img) {
int m = img.length, n = img[0].length;
int[][] result = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int count = 0, total = 0;
for (int ni = Math.max(0, i - 1); ni <= Math.min(m - 1, i + 1); ni++) {
for (int nj = Math.max(0, j - 1); nj <= Math.min(n - 1, j + 1); nj++) {
total += img[ni][nj];
count++;
}
}
result[i][j] = total / count;
}
}
return result;
}
}6 658
Дарим подписку на Яндекс Музыку
Ответьте на 1 вопрос и Яндекс Музыка ваша для вас и 3-х ваших близких.
Кинопоиск и Яндекс Книги тоже в подписке.
Попробуйте бесплатно❤️
Попробовать
#реклама 18+
music.yandex.ru
О рекламодателе
Реклама на Яндексе
6 658
Задача: 1245. Tree Diameter
Сложность: medium
Диаметр дерева - это количество ребер в самом длинном пути в этом дереве. Имеется неориентированное дерево из n узлов, помеченных от 0 до n - 1. Вам дан двумерный массив edges, где edges.length == n - 1 и edges[i] = [ai, bi] означает, что между узлами ai и bi в дереве есть неориентированное ребро. Верните диаметр дерева.
Пример:
Input: edges = [[0,1],[0,2]] Output: 2👨💻 Алгоритм: 1⃣Построение графа: Используем представление графа в виде списка смежности. 2⃣Поиск самой удаленной вершины (DFS1): Запускаем DFS от произвольной вершины (например, 0) для нахождения самой удаленной вершины от нее. 3⃣Поиск диаметра (DFS2): Запускаем DFS от найденной на предыдущем шаге самой удаленной вершины и находим самую удаленную вершину от нее. Это расстояние и будет диаметром дерева.reset(playerId): Устанавливаем счет игрока в 0. 😎 Решение:
import java.util.*;
public class Solution {
public int treeDiameter(int[][] edges) {
if (edges.length == 0) return 0;
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int[] edge : edges) {
graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
graph.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(edge[0]);
}
int[] farthestNode = new int[1];
int dfs(int node, int parent) {
int maxDepth = 0;
for (int neighbor : graph.get(node)) {
if (neighbor != parent) {
int depth = dfs(neighbor, node);
if (depth + 1 > maxDepth) {
maxDepth = depth + 1;
farthestNode[0] = neighbor;
}
}
}
return maxDepth;
}
dfs(0, -1);
int startNode = farthestNode[0];
dfs(startNode, -1);
return dfs(farthestNode[0], -1);
}
}6 658
Высшее образование дистанционно в Московском ВУЗе
Вы мечтаете получить высшее образование, но не сдали ЕГЭ или получили низкие баллы? У нас есть решение для вас!
Институт Международных Экономических Связей предлагает дистанционное обучение , которое позволяет получать качественные знания из любой точки мира по 10+ направлениям обучения.
✅ Государственный диплом без отметки о дистанте
✅ Удобный личный кабинет студента
✅ Поддержка кураторов на каждом этапе обучения
✅ Можно поступить без ЕГЭ
Узнать больше
#реклама 16+
imes.su
О рекламодателе
6 658
Задача: 1034. Coloring A Border
Сложность: medium
Вам дана целочисленная матричная сетка m x n и три целых числа row, col и color. Каждое значение в сетке представляет собой цвет квадрата сетки в данном месте. Два квадрата называются смежными, если они находятся рядом друг с другом в любом из 4 направлений. Два квадрата принадлежат одному связанному компоненту, если они имеют одинаковый цвет и являются смежными.
Граница связанного компонента - это все квадраты в связанном компоненте, которые либо смежны (по крайней мере) с квадратом, не входящим в компонент, либо находятся на границе сетки (в первой или последней строке или столбце). Вы должны окрасить границу связанного компонента, содержащего квадрат grid[row][col], в цвет. Верните конечную сетку.
Пример:
Input: grid = [[1,1],[1,2]], row = 0, col = 0, color = 3 Output: [[3,3],[3,2]]👨💻 Алгоритм: 1⃣Поиск связанного компонента: Используйте поиск в глубину (DFS) или поиск в ширину (BFS), чтобы найти все клетки, принадлежащие связанному компоненту, содержащему клетку grid[row][col]. Запомните все клетки, которые принадлежат этому компоненту. 2⃣Определение границ компонента: Для каждой клетки в связанном компоненте проверьте, является ли она границей. Клетка является границей, если она находится на краю сетки или если хотя бы одна из её соседних клеток не принадлежит связанному компоненту или имеет другой цвет. 3⃣Окрашивание границы: Измените цвет всех клеток, являющихся границами, на заданный цвет. 😎 Решение:
public class Solution {
public int[][] colorBorder(int[][] grid, int row, int col, int color) {
int m = grid.length, n = grid[0].length;
int originalColor = grid[row][col];
boolean[][] visited = new boolean[m][n];
List<int[]> borders = new ArrayList<>();
dfs(grid, row, col, originalColor, visited, borders);
for (int[] border : borders) {
grid[border[0]][border[1]] = color;
}
return grid;
}
private void dfs(int[][] grid, int r, int c, int color, boolean[][] visited, List<int[]> borders) {
int m = grid.length, n = grid[0].length;
visited[r][c] = true;
boolean isBorder = false;
for (int[] dir : new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}) {
int nr = r + dir[0], nc = c + dir[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
if (!visited[nr][nc]) {
if (grid[nr][nc] == color) {
dfs(grid, nr, nc, color, visited, borders);
} else {
isBorder = true;
}
}
} else {
isBorder = true;
}
}
if (isBorder || r == 0 || r == m - 1 || c == 0 || c == n - 1) {
borders.add(new int[]{r, c});
}
}
}6 658
Высшее образование дистанционно от 6700 ₽/мес.
Поступи в Московский технологический институт в июне!
— Высшее образование в московском вузе без выезда на сессии.
— Полностью дистанционный онлайн-формат.
— Обучайся дома, на работе, в путешествии.
— Диплом государственного образца.
— 73 направления и программы обучения.
— Программа колледж + вуз без ЕГЭ.
Скидка 10% на платное обучение при оплате за год.
Подать заявку
#реклама 16+
mti-vuz.ru
О рекламодателе
6 658
Задача: 472. Concatenated Words
Сложность: hard
Дан массив строк words (без дубликатов). Верните все составные слова из данного списка слов.
Составное слово определяется как строка, которая полностью состоит как минимум из двух более коротких слов (не обязательно различных) из данного массива.
Пример:
Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"] Output: ["catsdogcats","dogcatsdog","ratcatdogcat"] Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats"; "dogcatsdog" can be concatenated by "dog", "cats" and "dog"; "ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".👨💻 Алгоритм: 1⃣Для каждого слова в списке: Построить неявный граф, в котором узлы представляют индексы символов в слове, а ребра представляют возможность перехода от одного индекса к другому, если подстрока между ними является словом из списка. 2⃣Использовать поиск в глубину (DFS) для проверки, можно ли достигнуть узел с индексом word.length от узла с индексом 0 в графе. 3⃣Если узел word.length достижим от узла 0, добавить слово в ответ. 😎 Решение:
import java.util.*;
public class Solution {
private boolean dfs(String word, int length, boolean[] visited, Set<String> dictionary) {
if (length == word.length()) {
return true;
}
if (visited[length]) {
return false;
}
visited[length] = true;
for (int i = word.length() - (length == 0 ? 1 : 0); i > length; --i) {
if (dictionary.contains(word.substring(length, i)) && dfs(word, i, visited, dictionary)) {
return true;
}
}
return false;
}
public List<String> findAllConcatenatedWordsInADict(String[] words) {
Set<String> dictionary = new HashSet<>(Arrays.asList(words));
List<String> answer = new ArrayList<>();
for (String word : words) {
boolean[] visited = new boolean[word.length()];
if (dfs(word, 0, visited, dictionary)) {
answer.add(word);
}
}
return answer;
}
}6 658
Крупнейший университет искусственного интеллекта
Приглашаем на бесплатный однодневный интенсив по AI!
Освой искусственный интеллект для профессионального роста: создавай нейросети, автоматизируй бизнес-задачи и зарабатывай на AI-решениях.
✨ 8 000+ студентов со всего мира
✨ 600+ AI-проектов, созданных студентами
✨ Сборная Университета — победители крупнейших AI-хакатонов России
✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие)
✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие)
Будем рады видеть тебя в наших рядах!
Узнать больше
#реклама 16+
neural-university.ru
О рекламодателе
