1055. Shortest Way to Form String

LeetCode medium original: C# #csharp #leetcode #medium #string #two-pointers

Task text is translated from Russian for the selected interface language. Code is left unchanged.

LeetCode Static

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

Example:

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

Output: 2

C# solution

matched/original

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++ solution

auto-draft, review before submit

#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 solution

matched/original

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 solution

matched/original

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 solution

matched/original

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 solution

matched/original

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

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

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

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

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

😎

Vacancies for this task

Active vacancies with overlapping task tags are shown.

All vacancies

There are no active vacancies yet.