اطبع جميع الطرق الممكنة لكسر سلسلة في شكل قوس


مستوى الصعوبة الثابت
كثيرا ما يطلب في أمازون بلومبرغ جنرال إلكتريك للرعاية الصحية جونيبر نتوركس
العودية خيط

المشكلة بيان

في مشكلة "طباعة جميع الطرق الممكنة لكسر سلسلة في شكل قوس" ، قدمنا سلسلة "س". ابحث عن كل الطرق الممكنة لكسر السلسلة المحددة قوسشكل تي. قم بإحاطة جميع السلاسل الفرعية بين قوسين ().

نمط الإدخال

السطر الأول والوحيد الذي يحتوي على سلسلة "s".

تنسيق الإخراج

اطبع جميع الطرق الممكنة لكسر السلسلة المحددة في bracket_form. كل سطر يحتوي على سلسلة واحدة فقط.

القيود

  • 1 <= | ث | <= 10 ^ 3
  • يجب أن تكون s [i] أبجدية إنجليزية صغيرة

مثال

abcd
(a)(b)(c)(d)
(a)(b)(cd)
(a)(bc)(d)
(ab)(c)(d)
(ab)(cd)
(a)(bcd)
(abc)(d)
(abcd)

خوارزمية

هنا نستخدم العودية لحل هذه المشكلة. نحافظ على معلمتين: فهرس الحرف التالي المراد معالجته وسلسلة الإخراج حتى الآن. الآن ، ابدأ من فهرس الحرف التالي المراد معالجته. قم بإلحاق السلسلة الفرعية المكونة من السلسلة غير المعالجة بسلسلة الإخراج وتكرارها على السلسلة المتبقية حتى نقوم بمعالجة السلسلة بأكملها. نستخدم std :: substr لتشكيل سلسلة الإخراج. يعرض substr (pos ، n) سلسلة فرعية بطول n تبدأ من موضع نقطة البيع للسلسلة الحالية.

  1. نبدأ من فهرس الحرف التالي المراد معالجته.
  2. قم بإلحاق سلسلة فرعية مكونة من سلسلة غير معالجة بسلسلة الإخراج وتكرارها على المتبقي حتى نقوم بمعالجة السلسلة بأكملها.
  3. نستخدم substr (pos ، n) لتشكيل سلسلة الإخراج ، وهذا يعيد السلسلة الفرعية للطول n التي تبدأ من الموضع pos إذا كانت السلسلة الحالية.

تطبيق

برنامج C ++ لطباعة جميع الطرق الممكنة لكسر سلسلة في شكل قوس

#include <bits/stdc++.h>
using namespace std;

void find_next(string s, int in, string t)
{
  if(in==s.length())
  {	
      cout<<t<<endl;
  }
  for(int i=in;i<s.length(); i++)
  {
      string temp = t;
      temp+="(";
      temp+=s.substr(in,i+1-in);
      temp+=")";
    find_next(s, i+1 , temp);
  }
}

int main()
{
  string s;
  cin>>s;
  find_next(s,0,"");
  return 0;
}

برنامج جافا لطباعة جميع الطرق الممكنة لكسر سلسلة في شكل قوس

import java.util.Scanner;

class sum
{
    public static void find_next(String s, int in, String t)
    {
        if(in==s.length())
  {	
      System.out.println(t);
  }
  for(int i=in;i<s.length(); i++)
  {
      String temp = t;
      temp+="(";
      temp+=s.substring(in,i+1);
      temp+=")";
    find_next(s, i+1 , temp);
  }
    }
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        String s = sr.next();
        find_next(s,0,"");
    }
}




tutcup
(t)(u)(t)(c)(u)(p)
(t)(u)(t)(c)(up)
(t)(u)(t)(cu)(p)
(t)(u)(t)(cup)
(t)(u)(tc)(u)(p)
(t)(u)(tc)(up)
(t)(u)(tcu)(p)
(t)(u)(tcup)
(t)(ut)(c)(u)(p)
(t)(ut)(c)(up)
(t)(ut)(cu)(p)
(t)(ut)(cup)
(t)(utc)(u)(p)
(t)(utc)(up)
(t)(utcu)(p)
(t)(utcup)
(tu)(t)(c)(u)(p)
(tu)(t)(c)(up)
(tu)(t)(cu)(p)
(tu)(t)(cup)
(tu)(tc)(u)(p)
(tu)(tc)(up)
(tu)(tcu)(p)
(tu)(tcup)
(tut)(c)(u)(p)
(tut)(c)(up)
(tut)(cu)(p)
(tut)(cup)
(tutc)(u)(p)
(tutc)(up)
(tutcu)(p)
(tutcup)

تحليل التعقيد لطباعة جميع الطرق الممكنة لكسر سلسلة في شكل قوس

تعقيد الوقت

O (ن ^ 2) أين n هو حجم السلسلة "s".

تعقيد الفضاء

O (ن ^ 2) أين n هو حجم السلسلة. هنا نعلن سلسلة بعد كل حرف للحصول على الإجابة.