【算法】字节跳动编程题-双生词

题目描述

双生词

双生词是指满足如下条件的两个字符串：（假设两个字符串分别为S和S’）

1. 字符串长度相同
2. 将字符串S收尾绕成环，再选一个位置切开，顺时针或逆时针能够得到字符串S’
           

容易得到，若s与S’为双生词，则s’与s也为双生词

给定一批仅有英文小写字母组成的字符串，询问他们之中是否存在双生词

输入描述

首先给出测试组数t，表示一共有多少组数据

对于每组数据，第一行为一个整数n,表示一共有多少个字符串。接下来n行，每行一个字符串

思路

判断str1和str2是否为双生词很简单:

str = str1+str1 //解决收尾相连的问题

比较 str2是否为str中的子串，若是，则返回true

比较 str2.reverser()是否为str中的子串，若是，返回true //解决逆时针循环的问题

否则返回false

样例

输入

3
2
Helloworld
Hdlrowolle
2
Helloworld
Worldhello
2
Abcde
Acbde
           

输出

Yeah
Yeah
Sad
           

JavaScript实现

const twins = (str1,str2) => {
    print("str1:",str1,"str2:",str2);
    if(str1.length != str2.length){
        return false;
    }
    let str = str1+str1;
    print("str:",str);
    if(str.indexOf(str2) != -1){    
        return true;
    }
    //let str3 = str2.reverse(); //翻转str2
    //字符串翻转
    var newstr = str2.split("").reverse().join("");
    print("new:",newstr);
    if(str.indexOf(newstr) != -1){    
        //print(str,str2);
        return true;
    }
    return false;
}
var m = parseInt(readline());
for(let i = 0; i < m; i++){
    var n = parseInt(readline());
    let arr = [];
    for (let j = 0; j < n; j++) {
        let line2 = readline();
        //arr.push(line2.split(''));//数组
        arr.push(line2);//字符串
    }
    
    let flag = false;
    find:
    for(let j = 0; j < n; j++){
        for(let k = j+1; k < n; k++){
            if(twins(arr[j], arr[k])){
                flag = true;
                print("true");
                break find;
            }
        }
    }
    if(!flag){
        print(false);
    }
}
           

c++实现

c++实现2

Python实现

JavaScript字符串翻转

var newstr = str2.split("").reverse().join("");
           

JavaScript二维数组输入

var n = parseInt(readline());
        let arr = [];
        for (let j = 0; j < n; j++) {
            let line2 = readline();
            arr.push(line2.split(''));//数组
            //arr.push(line2);//字符串
    }
           

JavaScript字符串输入

var n = parseInt(readline());
        let arr = [];
        for (let j = 0; j < n; j++) {
            let line2 = readline();
            //arr.push(line2.split(''));//数组
            arr.push(line2);//字符串
        }