1415. رشته واژگانی K-Th از تمام رشته های شاد طول n

1415. رشته واژگانی K-Th از تمام رشته های شاد طول n

مشکل: واسطه

مباحث: Stringبا Backtracking

بوها رشته مبارک رشته ای است که:

• فقط از نامه های مجموعه تشکیل شده است ['a', 'b', 'c']بشر
• s[i] != s[i + 1] برای همه ارزشهای i از 1 به s.length - 1 (رشته 1 شاخص است).

به عنوان مثال ، رشته ها “ABC”با “AC”با “ب” وت “ABCBABCBCB” همه رشته ها و رشته ها خوشحال هستند “AA”با “Baa” وت “ رشته های شاد نیستند

با توجه به دو عدد صحیح n وت k، لیستی از تمام رشته های شاد طول را در نظر بگیرید n طبقه بندی شده به ترتیب واژگان شناسی.

بازگشت رشته KTH این لیست یا بازگشت رشته اگر کمتر از k رشته های مبارک طول nبشر

مثال 1:

• ورودی: n = 1 ، k = 3
• خروجی: “ج”
• توضیح: لیست [“a”, “b”, “c”] شامل تمام رشته های شاد از طول 1. رشته سوم “C” است.

مثال 2:

• ورودی: n = 1 ، k = 4
• خروجی: “”
• توضیح: فقط 3 رشته شاد از طول 1 وجود دارد.

مثال 3:

• ورودی: n = 3 ، k = 9
• خروجی: “کابین”
• توضیح: 12 رشته شاد مختلف از طول 3 وجود دارد [“aba”, “abc”, “aca”, “acb”, “bab”, “bac”, “bca”, “bcb”, “cab”, “cac”, “cba”, “cbc”]بشر 9th String = “CAB” را پیدا خواهید کرد

محدودیت ها:

• 1 <= n <= 10
• 1 <= k <= 100

نکته:

1. تمام رشته های شاد طول n را به صورت بازگشتی ایجاد کنید.
2. آنها را به ترتیب واژگونی مرتب کنید و در صورت وجود رشته KTH را برگردانید.

راه حل:

ما باید تمام رشته های شاد ممکن با طول معین را تولید کنیم n و رشته k-th را به ترتیب واژگونی برگردانید. یک رشته شاد به عنوان رشته ای متشکل از شخصیت های “A” ، “B” و “C” تعریف می شود که در آن هیچ دو شخصیت متوالی یکسان نیستند.

رویکرد

1. رشته های شاد ایجاد کنید: برای تولید تمام رشته های شاد ممکن از طول ، از یک رویکرد backtracking استفاده کنید nبشر این شامل ساخت مجدد شخصیت رشته ها به صورت شخصیت است و اطمینان حاصل می کند که هر شخصیت جدید با شخصیت قبلی متفاوت است.
2. اعتبار k را بررسی کنید: اگر تعداد رشته های شاد تولید شده کمتر از باشد k، یک رشته خالی را برگردانید.
3. رشته k-th را برگردانید: از آنجا که رشته های تولید شده به دلیل ترتیب انتخاب شخصیت (“A” ، “B” ، “C”) به ترتیب واژگونی هستند ، ما می توانیم به طور مستقیم به عنصر K-TH (تنظیم برای فهرست بندی 1 مبتنی بر) دسترسی پیدا کنیم.

بیایید این راه حل را در PHP پیاده سازی کنیم: 1415. رشته واژگانی K-Th از تمام رشته های شاد طول n

/**
 * @param Integer $n
 * @param Integer $k
 * @return String
 */
function getHappyString($n, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param $current
 * @param $remaining
 * @param $last_char
 * @param $result
 * @return void
 */
function generate($current, $remaining, $last_char, &$result) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo getHappyString(1, 3) . "\n"; // Output: "c"
echo getHappyString(1, 4) . "\n"; // Output: ""
echo getHappyString(3, 9) . "\n"; // Output: "cab"
?>

توضیح:

1. نسل پشتی: generate عملکرد رشته های شاد را با بیان مجدد شخصیت های “A” ، “B” یا “C” به رشته فعلی می سازد ، و اطمینان می دهد که هر شخصیت جدید با آخرین متفاوت است. این کار با بررسی در برابر شخصیت قبلی انجام می شود (last_char).
2. مورد پایه: هنگامی که طول باقی مانده پر شود (remaining) به 0 می رسد ، رشته فعلی به لیست نتیجه اضافه می شود.
3. نظم: با تکرار شخصیت ها به ترتیب “A” ، “B” ، “C” در هر مرحله ، رشته های تولید شده به طور طبیعی بدون نیاز به مرتب سازی صریح به ترتیب واژگان شناسی هستند.
4. کارایی: این رویکرد به طور مؤثر تمام رشته های معتبر را تولید می کند و تعداد را در برابر آن بررسی می کند k، اطمینان از اینکه ما فقط رشته های لازم را تولید می کنیم و در صورت اعتبار به طور مستقیم به عنصر K-Th دسترسی پیدا می کنیم.

این روش تضمین می کند که ما تمام رشته های خوشحال کننده ممکن را به صورت بهینه تولید می کنیم و از ترتیب واژگان طبیعی انتخاب شخصیت برای جلوگیری از مرتب سازی استفاده می کنیم و در نتیجه یک راه حل کارآمد ایجاد می شود.

پیوندهای تماس

اگر این سریال را مفید دیدید ، لطفاً در نظر بگیرید مخزن یک ستاره در GitHub یا به اشتراک گذاری پست در شبکه های اجتماعی مورد علاقه خود. حمایت شما برای من بسیار معنی دارد!

اگر می خواهید مطالب مفید تری مانند این ، احساس راحتی کنید که از من پیروی کنید: