分割四個不同的字符串  


難度級別 容易獎學金
經常問 埃森哲 土磚 GoDaddy的 雜貨店 霍尼韋爾 Quora的 Splunk的

問題陳述  

在“分割四個不同的字符串”問題中,我們必須檢查給定的輸入 可以分為4個字符串,這樣每個字符串都是非空的並且彼此不同。

輸入格式  

第一個也是唯一一個包含字符串“ s”的孤行。

輸出格式  

如果將給定的字符串分為四個不相等的子字符串,則打印“是”,否則打印“否”。

約束  

  • 1 <= | s | <= 10 ^ 6
  • s [i]必須是小寫字母

例  

tutorialscup
Yes

說明: 在這裡,我們知道字符串的長度大於10,然後我們可以輕鬆地將字符串分解為長度為1、2、3和n-6的子字符串,其中n是給定字符串“ s”的長度。

aabab
No

分割四個不同字符串的算法  

1. 如果字符串的長度大於或等於10,則返回true。 在此,如果長度等於10,則可以形成長度分別為1、2、3、4的字符串。 因此,返回true。

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) 因為我們在這裡不使用任何輔助空間。 在這裡,我們只計算答案,而不存儲任何數據。