753. Cracking the Safe

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

LeetCode Static

Имеется сейф, защищенный паролем. Пароль представляет собой последовательность из n цифр, каждая из которых может находиться в диапазоне [0, k - 1]. Сейф имеет особый способ проверки пароля. Например, правильный пароль - "345", а вы вводите "012345": после ввода 0 последние 3 цифры - "0", что неверно. После ввода 1 последние 3 цифры - "01", что неверно. После ввода 2 последние 3 цифры - "012", что неверно.

После ввода 3 последние 3 цифры - "123", что неверно. После ввода 4 последние 3 цифры - "234", что неверно. После ввода 5 последние 3 цифры - "345", что верно, и сейф разблокируется. Верните любую строку минимальной длины, которая разблокирует сейф на определенном этапе ввода.

Пример:

Input: n = 1, k = 2

Output: "10"

C# решение

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

using System.Collections.Generic;
using System.Text;
public class Solution {
    public string CrackSafe(int n, int k) {
        var seen = new HashSet<string>();
        var result = new StringBuilder();
        string startNode = new string('0', n - 1);
        Dfs(startNode, k, seen, result);
        result.Append(startNode);
        return result.ToString();
    }
    private void Dfs(string node, int k, HashSet<string> seen, StringBuilder result) {
        for (int x = 0; x < k; x++) {
            string neighbor = node + x;
            if (!seen.Contains(neighbor)) {
                seen.Add(neighbor);
                Dfs(neighbor.Substring(1), k, seen, result);
                result.Append(x);
            }
        }
    }
}

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 string CrackSafe(int n, int k) {
        var seen = new HashSet<string>();
        var result = new StringBuilder();
        string startNode = new string('0', n - 1);
        Dfs(startNode, k, seen, result);
        result.Append(startNode);
        return result.ToString();
    }
    private void Dfs(string node, int k, HashSet<string> seen, StringBuilder result) {
        for (int x = 0; x < k; x++) {
            string neighbor = node + x;
            if (!seen.Contains(neighbor)) {
                seen.push_back(neighbor);
                Dfs(neighbor.Substring(1), k, seen, result);
                result.Append(x);
            }
        }
    }
}

Java решение

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

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public String crackSafe(int n, int k) {
        Set<String> seen = new HashSet<>();
        StringBuilder result = new StringBuilder();

        String startNode = "0".repeat(n - 1);
        dfs(startNode, k, seen, result);

        result.append(startNode);
        return result.toString();
    }

    private void dfs(String node, int k, Set<String> seen, StringBuilder result) {
        for (int x = 0; x < k; x++) {
            String neighbor = node + x;
            if (!seen.contains(neighbor)) {
                seen.add(neighbor);
                dfs(neighbor.substring(1), k, seen, result);
                result.append(x);
            }
        }
    }
}

JavaScript решение

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

var crackSafe = function(n, k) {
    const seen = new Set();
    const result = [];

    const dfs = (node) => {
        for (let x = 0; x < k; x++) {
            const neighbor = node + x;
            if (!seen.has(neighbor)) {
                seen.add(neighbor);
                dfs(neighbor.slice(1));
                result.push(x);
            }
        }
    };

    const startNode = '0'.repeat(n - 1);
    dfs(startNode);
    return startNode + result.join('');
};

Python решение

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

def crackSafe(n, k):
    seen = set()
    result = []

    def dfs(node):
        for x in range(k):
            neighbor = node + str(x)
            if neighbor not in seen:
                seen.add(neighbor)
                dfs(neighbor[1:])
                result.append(str(x))

    start_node = '0' * (n - 1)
    dfs(start_node)
    return start_node + ''.join(result)

Go решение

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

package main

import (
    "fmt"
    "strings"
)

func crackSafe(n int, k int) string {
    seen := make(map[string]bool)
    var result []byte

    startNode := strings.Repeat("0", n-1)
    dfs(startNode, k, seen, &result)

    result = append(result, startNode...)
    return string(result)
}

func dfs(node string, k int, seen map[string]bool, result *[]byte) {
    for x := 0; x < k; x++ {
        neighbor := node + fmt.Sprint(x)
        if !seen[neighbor] {
            seen[neighbor] = true
            dfs(neighbor[1:], k, seen, result)
            *result = append(*result, byte(x+'0'))
        }
    }
}

Algorithm

Создайте граф, где каждая вершина представляет собой строку длины n-1, а каждое ребро между двумя вершинами представляет собой добавление одной из цифр из диапазона [0, k-1].

Используйте алгоритм Эйлерова пути или цикла для нахождения пути, который проходит через каждое ребро ровно один раз.

Составьте итоговую строку, которая включает начальную вершину и все добавленные цифры.

😎

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

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

Все вакансии

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