Төрт жолды бөлу


Күрделілік дәрежесі оңай
Жиі кіреді Accenture Adobe GoDaddy Грейфтерлер Honeywell Quora Splunk
String

Проблемалық мәлімдеме

«Төрт жолды бөлу» мәселесінде берілген кірісті тексеру керек жол әр жол бос емес және бір-бірінен өзгеше болатындай етіп 4 жолға бөлінуі мүмкін.

Кіріс форматы

«S» жолынан тұратын жалғыз және жалғыз.

Шығу форматы

Егер берілген жолды төрт тең емес ішкі жолға бөлетін болсақ, «Иә» басып шығарыңыз, басқа жағдайда «Жоқ» басып шығарыңыз.

Шектеу

  • 1 <= | s | <= 10 ^ 6
  • s [i] кіші әріптер алфавиті болуы керек

мысал

tutorialscup
Yes

Түсіндіру: Бұл жерде біз жіптің ұзындығы 10-нан асатынын білеміз, сонда біз жолды ұзындығы 1, 2, 3 және n-6 ішкі тізбектеріне оңай кіре аламыз, мұндағы n - берілген «s» жолының ұзындығы.

aabab
No

Төрт жолды бөлудің алгоритмі

1. Егер жолдың ұзындығы 10-нан үлкен немесе тең болса, шындық мәніне оралыңыз. Мұнда, егер ұзындық 10-ға тең болса, онда ұзындығы 1, 2, 3, 4 бөлек болатын жолдар құруға болады. Сонымен, шындыққа оралыңыз.

2. Қалған күштер техникасы әр түрлі және берілген кіріс жолын құра алатын төрт жолды табуға бағытталған.

Іске асыру

Төрт жолды бөлуге арналған C ++ бағдарламасы

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    string str;
    cin>>str;
    int flag=0;
    if (str.length() >= 10)
    {
        flag=1;
    }
    for (int i = 1; i < str.size(); i++)
    {
        for (int j = i + 1; j < str.size(); j++)
        {
            for (int k = j + 1; k < str.size(); k++)
            {
                string sub1 = str.substr(0, i);
                string sub2 = str.substr(i, j - i);
                string sub3 = str.substr(j, k - j);
                string sub4 = str.substr(k, str.size() - k);
                if(sub1 != sub2 && sub1 != sub3 && sub1 != sub4 && sub2 != sub3 && sub2 != sub4 && sub3 != sub4)
                {
                    flag=1;
                    goto label;
                }
            }
        }
    } 
    label:;
    if(flag)
    {
        cout<<"Yes"<<endl;
    }
    else
    {
        cout<<"No"<<endl;
    }
    return 0;
}

Төрт жолды бөлуге арналған Java бағдарламасы

import java.util.Scanner;

class sum
{ 
  public static boolean strcheck(String s1, String s2) 
  { 
    if(s1.compareTo(s2) != 0)
                {
                    return true;
                }
                return false;
  } 
  public static void main(String[] args) 
  { 
    Scanner sr = new Scanner(System.in); 
                String s = sr.next();
                int flag=0;
    if(s.length()>=10)
                {
                    flag=1;
                }
    else
                { 
                    for (int i = 1; i < s.length(); i++) 
                    { 
                            for (int j = i + 1; j < s.length(); j++) 
                            { 
                                    for (int k = j + 1; k < s.length(); k++) 
                                    { 
                                            String s1 = "", s2 = "", s3 = "", s4 = ""; 
                                            s1 = s.substring(0, i); 
                                            s2 = s.substring(i, j); 
                                            s3 = s.substring(j, k); 
                                            s4 = s.substring(k, s.length());
                                            if(strcheck(s1, s2) && strcheck(s1, s3) && strcheck(s1, s4) && strcheck(s2, s3) && strcheck(s2, s4) && strcheck(s3, s4)) 
                                            {
                                                    flag=1; 
                                            }
                                    } 
                            } 
                    } 
                }
                if(flag==1)
                {
                    System.out.println("Yes");
                }
                else
                {
                    System.out.println("No");
                }
  } 
} 
abcd
Yes

Төрт жолды бөлуге арналған күрделілікті талдау

Уақыттың күрделілігі

Егер жіптің ұзындығы 10-нан үлкен немесе тең болса, онда уақыттың күрделілігі O (1). Әйтпесе, уақыттың күрделілігі болады O (n ^ 4) Мұндағы n - «s» жолының өлшемі.

Ғарыштың күрделілігі

O (1) өйткені біз бұл жерде ешқандай қосалқы кеңістікті қолданбаймыз. Мұнда біз ешбір дерек сақтамай, жауабын есептейміз.