1055. Shortest Way to Form String

LeetCode medium оригинал: C# #csharp #leetcode #medium #string #two-pointers

LeetCode Static

Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (например, "ace" является подпоследовательностью "abcde", а "aec" - нет). Если даны две строки source и target, верните минимальное количество подпоследовательностей source, чтобы их объединение равнялось target. Если задача невыполнима, верните -1.

Пример:

Input: source = "abc", target = "abcbc"

Output: 2

C# решение

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

public class Solution {
    public int MinSubsequences(string source, string target) {
        int subsequencesCount = 0;
        int targetIndex = 0;
        while (targetIndex < target.Length) {
            int sourceIndex = 0;
            subsequencesCount++;
            int startIndex = targetIndex;
            while (sourceIndex < source.Length && targetIndex < target.Length) {
                if (source[sourceIndex] == target[targetIndex]) {
                    targetIndex++;
                }
                sourceIndex++;
            }
            if (targetIndex == startIndex) {
                return -1;
            }
        }
        return subsequencesCount;
    }
}

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 int MinSubsequences(string source, string target) {
        int subsequencesCount = 0;
        int targetIndex = 0;
        while (targetIndex < target.size()) {
            int sourceIndex = 0;
            subsequencesCount++;
            int startIndex = targetIndex;
            while (sourceIndex < source.size() && targetIndex < target.size()) {
                if (source[sourceIndex] == target[targetIndex]) {
                    targetIndex++;
                }
                sourceIndex++;
            }
            if (targetIndex == startIndex) {
                return -1;
            }
        }
        return subsequencesCount;
    }
}

Java решение

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

public class Solution {
    public int minSubsequences(String source, String target) {
        int subsequencesCount = 0;
        int targetIndex = 0;

        while (targetIndex < target.length()) {
            int sourceIndex = 0;
            subsequencesCount++;
            int startIndex = targetIndex;

            while (sourceIndex < source.length() && targetIndex < target.length()) {
                if (source.charAt(sourceIndex) == target.charAt(targetIndex)) {
                    targetIndex++;
                }
                sourceIndex++;
            }

            if (targetIndex == startIndex) {
                return -1;
            }
        }

        return subsequencesCount;
    }
}

JavaScript решение

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

function minSubsequences(source, target) {
    let subsequencesCount = 0;
    let targetIndex = 0;

    while (targetIndex < target.length) {
        let sourceIndex = 0;
        subsequencesCount++;
        let startIndex = targetIndex;

        while (sourceIndex < source.length && targetIndex < target.length) {
            if (source[sourceIndex] === target[targetIndex]) {
                targetIndex++;
            }
            sourceIndex++;
        }

        if (targetIndex === startIndex) {
            return -1;
        }
    }

    return subsequencesCount;
}

Python решение

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

def minSubsequences(source, target):
    subsequences_count = 0
    target_index = 0

    while target_index < len(target):
        source_index = 0
        subsequences_count += 1
        start_index = target_index

        while source_index < len(source) and target_index < len(target):
            if source[source_index] == target[target_index]:
                target_index += 1
            source_index += 1

        if target_index == start_index:
            return -1

    return subsequences_count

Go решение

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

package main

func minSubsequences(source, target string) int {
    subsequencesCount := 0
    targetIndex := 0

    for targetIndex < len(target) {
        sourceIndex := 0
        subsequencesCount++
        startIndex := targetIndex

        for sourceIndex < len(source) && targetIndex < len(target) {
            if source[sourceIndex] == target[targetIndex] {
                targetIndex++
            }
            sourceIndex++
        }

        if targetIndex == startIndex {
            return -1
        }
    }

    return subsequencesCount
}

Algorithm

Используй два указателя для отслеживания текущих позиций в строках source и target.

Перебирай символы строки source, пока не найдешь совпадающий символ в target.

Если ты прошел всю строку source и не нашел все символы target, увеличь счетчик количества подпоследовательностей и начни снова с начала source.

Повтори шаги 2 и 3 до тех пор, пока не пройдешь всю строку target.

😎

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

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

Все вакансии

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