字符串连接切割---双生词

问题描述

对于任意给定的两个字符串A,B, 如果字符串A首位环绕相接, 然后选择某一个位置切割开, 顺时针或者逆时针读取, 与B字符串相同, 则称A,B是双生词. 对于给定的n组字符串, 判定其中是否纯在双生词.

输入

1 2 helloworld worldhello

输出

Yeah

解题思路

1. 双生词基本特点 (1). 长度相同 (2). 所含字母相同
2. 依次将两组字符中的一个字符按照首位相接然后切割, 判断能否组成另外一个字符串

代码实现

#include <iostream>
#include <string>
#include<set>
#include<map>
#include <algorithm>
#include <vector>
using namespace std;

bool IsTwinString(const string & str1,const string & str2)
{
          
   
    if(str1==str2)
    {
          
   
        return 1;
    }

    string strTemp1 = str1;
    reverse(strTemp1.begin(),strTemp1.end());
    if(strTemp1==str2)
    {
          
   
        return 1;
    }

    string strTemp2 = str2;
    sort(strTemp1.begin(),strTemp1.end());
    sort(strTemp2.begin(),strTemp2.end());
    if(strTemp1!=strTemp2)
    {
          
   
        return 0;
    }

    string strTemp3;
    char ch = str2[0];
    //选择切割点
    for(int i=1; i<str1.length()-1; i++)
    {
          
   
        //起始开头的字母要一样
        if(str1[i-1]!=ch&&str1[i]!=ch)
        {
          
   
            continue;
        }

        strTemp1 = str1;
        strTemp2 = strTemp1.substr(i);
        strTemp1.erase(i,str1.length());
        //逆时针
        if(str1[i]==ch)
        {
          
   
            strTemp3 = strTemp2+strTemp1;
            if(strTemp3==str2)
            {
          
   
                return 1;
            }
        }

        //顺时针
        if(str1[i-1]==ch)
        {
          
   
            reverse(strTemp2.begin(),strTemp2.end());
            reverse(strTemp1.begin(),strTemp1.end());
            strTemp3 = strTemp1+strTemp2;
            if(strTemp3==str2)
            {
          
   
                return 1;
            }
        }
    }

    return 0;
}

int main()
{
          
   
    int iTestNum;
    int iStrNum;
    cin>>iTestNum;
    string strTemp;
    vector<string> vStr;
    while(iTestNum--)
    {
          
   
        cin>>iStrNum;
        vStr.clear();
        for(int i=0; i<iStrNum; i++)
        {
          
   
            cin>>strTemp;
            vStr.push_back(strTemp);
        }

        bool bHasFind = 0;
        for(int i=0; i<iStrNum-1; i++)
        {
          
   
            for(int j=i+1; j<iStrNum; j++)
            {
          
   
                if(vStr[i].length()==vStr[j].length()&&IsTwinString(vStr[i],vStr[j]))
                {
          
   
                    bHasFind = 1;
                    break;
                }
            }
            if(bHasFind)
            {
          
   
                break;
            }
        }

        if(bHasFind)
        {
          
   
            cout<<"Yeah"<<endl;
        }
        else
        {
          
   
            cout<<"Sad"<<endl;
        }
    }
    return 0;
}