首页 > 试题广场 >

寄居蟹与海葵

[编程题]寄居蟹与海葵
  • 热度指数:383 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
寄居蟹与海葵是一对合作互助的共栖伙伴。海葵是寄居蟹最称职的门卫。它用有毒的触角去蜇那些敢来靠近它们的所有动物,保护寄居蟹。 而寄居蟹则背着行动困难的海葵,四出觅食,有福同享。
但并不是所有寄居蟹和海葵都可以做搭档的。那就要看海葵的身体是不是符合寄居蟹的螺壳。
海葵的身体是有褶皱的,而寄居蟹的螺壳同样凹凸不平,我们可以用一个大写字母组成的字符串来表示它们的高低程度, 其中A代表0,B代表1,依次类推。我们称两者相加等于25的就算是吻合,比如A和Z相吻合,B与Y吻合,依次类推。
只要海葵身体的部分序列与寄居蟹外壳的序列相吻合,就称他们可以一起生活。
比如:
1.海葵的褶皱是"ABCDEFG",寄居蟹是"ZYXWVUT"。这样,它们就可以完全吻合了。
2.海葵的褶皱是"AHBICJDKELFMGN",寄居蟹是"ZYXWVUT"。这样,寄居蟹可以和海葵的部分序列"ABCDEFG"相吻合 (注意:部分序列不改变字符原来的先后顺序,比如"ACB"就不是它的部分序列)。
3.海葵的褶皱是"ABCD",寄居蟹是"ZYXWVUT"。这样,虽然海葵可以和寄居蟹前面一段完全吻合,但它比寄居蟹要小, 不能完全保护寄居蟹的安全,所有它们是不适合的。
4.海葵的褶皱是"HIJKLMNOPQ",寄居蟹是"ZYXWVUT"。这样,它们就可以完全不吻合了。
现给你两段字符串S1、S2,分别代表海葵和寄居蟹的外壳,为了它们以后各都能快乐地生活,请你帮忙计算一下它们是不是吻合的。

输入描述:
输入包括多组测试数据。
每组测试数据包括两个字符串H、J,分别代表海葵的外壳和寄居蟹的外壳。可以保证它们的长度都小于100000。
输入以0 0结束。


输出描述:
如果寄居蟹和海葵的外壳能吻合,就输出"Yes",否则输出"No"。
示例1

输入

ABCDEFG ZYXWVUT
AHBICJDKELFMGN ZYXWVUT
ABCD ZYXWVUT
HIJKLMNOPQ ZYXWVUT
0 0

输出

Yes
Yes
No
No

python解法with注释

import sys


def canFit(str1, str2):
    # 如果str2长度大于str1,返回false
    if len(str2) > len(str1): return False
    # 期望吻合的字符串,如str2=“ZYXW”,那么expectString="ABCD"
    expectString = ""
    for i in str2:
        expectString += chr(155 - ord(i))
    # 贪心算法,看str1里有没有expectString。(参考All-in-all这道题目)
    for i in str1:
        if expectString and expectString[0] == i:
            expectString = expectString[1:]
    return True if not expectString else False


for i in sys.stdin.readlines():
    if not i.startswith("0"):
        str1, str2 = i.strip().split()
        print("Yes" if canFit(str1, str2) else "No")
发表于 2017-11-16 18:31:14 回复(0)
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<functional>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <exception>
#include <iomanip>
#include <memory>
#include <sstream>
#define INF 1000000
using namespace std;
int main(int argc, char** argv)
{
 //freopen("in.txt", "r", stdin);
 string s1, s2;
 while (cin >> s1 >> s2 && s1 != "0" && s2 != "0")
 {
  int m = s1.size(), n = s2.size();
  if (m < n)
  {
   cout << "No" << endl;
   continue;
  }
  int i = 0, j = 0;
  while (i < m && j < n)
  {
   if (s1[i] + s2[j] == 'A' + 'Z')
   {
    ++i;
    ++j;
   }
   else
    ++i;
  }
  cout << (j == n ? "Yes" : "No") << endl;
 }
 return 0;
}

发表于 2017-07-19 10:22:02 回复(0)
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			char[] H = sc.next().toCharArray();
			char[] J = sc.next().toCharArray();
			if(H[0] == '0' && J[0] == '0') break;
			if(H.length < J.length) {
				System.out.println("No");
				continue;
			}
			for (int i = 0; i < J.length; i ++ ) {
				J[i] = (char)('A' + 'Z' - J[i]);
			}
			int i = 0, j = 0;
			while (i < H.length && j < J.length) {
				if(H[i] == J[j]) j ++ ;
				i ++ ;
			}
			if(j == J.length) System.out.println("Yes");
			else System.out.println("No");
		}
	}
}

编辑于 2016-10-13 22:00:05 回复(0)
匹配一下就好了
#include <iostream>
#include <string>
using namespace std;

bool check(string & str, string & sub)
{
	const string shell = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
	const string crab  = "ZYXWVUTSRQPONMLKJIHGFEDCBA";
	if (str.size() < sub.size()) return false;

	int i = 0, j = 0;
	for (; i < str.size() && j < sub.size(); ++i)
	{
		if (shell[str[i] - 'A'] == crab[sub[j] - 'A'])
			++j;
	}
	if (j == sub.size()) return true;
	else return false;
}

int main()
{
	string str, sub;
	while (cin >> str >> sub && (str != "0" || sub != "0"))
	{
		cout << (check(str, sub) ? "Yes" : "No") << endl;
	}
	return 0;
}

编辑于 2015-12-20 13:58:26 回复(1)
// write your code here cpp\
#include<stdio.h>
#include<string.h>
char str1[100010],str2[100010];
int main(){
    while(scanf("%s %s",str1,str2)){
        int len1=strlen(str1);
        int len2=strlen(str2);
        if(len1==1&&len2==1&&str1[0]=='0'&&str2[0]=='0')
            break;
        int i,j=0;
        for(i=0;i<len1;++i){
        if(str1[i]-'A'+str2[j]-'A'==25)
            j++;
        }
        if(j>=len2)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

编辑于 2020-03-30 21:08:50 回复(0)
防止超时和超过规定内存,最好不要把中间的数据存储下来,直接计算得出累加值;
#include<iostream>
#include<string>
using namespace std;
int main()
{
	string str, res;
	while (cin >> str >> res)
	{
		if (str == "0"&&res == "0")
			break;
		if (str.length() < res.length())
		{
			cout << "No" << endl;
			continue;
		}
		int cnt = 0, j = 0;
		int strvalue, resvalue = res[j] - 'A';
		for (int i = 0; i < str.length(); i++)
		{
			strvalue = str[i] - 'A';
			if (strvalue + resvalue == 25)
			{
				cnt++;
				if (j != res.length() - 1)
					resvalue = res[++j] - 'A';
				else
					break;
			}
		}
		if (cnt == res.length())
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
	return 0;
}

发表于 2017-04-24 12:58:04 回复(0)
#include <iostream>
#include <string>
using namespace std;
int main()
{
    string A,B;
    while(cin>>A>>B && (A != "0" || B != "0"))
    {
	if(A.size()<B.size())
		cout<<"No"<<endl;
        else
        {
            int i=0,pos=0;
            for(i=0;i<B.size();++i)
            {
                char c='A'+25-(B[i]-'A');           
                string::size_type p=A.find(c,pos);
                if(p==-1)
                    break;
                else
                    pos=p;
            }
            if(i==B.size())
                cout<<"Yes"<<endl;
            else
                cout<<"No"<<endl;
        }
    }
}


发表于 2016-08-31 22:05:36 回复(0)
var readline = require('readline');
const rl = readline.createInterface({
        input: process.stdin,
        output: process.stdout
});
var data=[];
rl.on('line', function(line){
    if(line=='0 0'){
        return ;
    }
    data=line.split(' ');
    var H=data[0];
    var H_length=data[0].length;
    var J=data[1];
    var J_length=data[1].length;
    if(H_length<J_length){
        console.log('No');
        return ;
    }else{
        var index=0;//记录H中已搜寻到与J吻合的位置index开始往后搜索
        var value='A'.charCodeAt(0);
        for(var j=0;j<J_length;j++){
            var Flag=0;//用于判断是否找到第j个寄居蟹吻合的海葵
            for(var h=index;h<H_length;h++){
                var J_value=J[j].charCodeAt(0)-value;
                var H_value=H[h].charCodeAt(0)-value;
                if(J_value+H_value==25){
                    index=h;//搜索到与J吻合的H中的位置
                    Flag=1;//搜索到吻合的,则置为1.
                    break;
                }
            }
            if(Flag!=1){
                console.log('No');
                return ;//一旦有一个J没有找到吻合的H,则输出No
            }
        }
        console.log('Yes');
        return ;
    } 
})

发表于 2016-08-30 15:37:10 回复(0)
粗略的写下,应该还能再改进
public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String[] a = new String[100];// 先开100的空间
		String[] b = new String[100];
		int i = 0;// 实际输入的数组个数
		while (i < 100) {
			a[i] = sc.next();
			b[i] = sc.next();
			if (a[i].equals("0") && b[i].equals("0"))
				break;
			i++;
		}
		JjJuXie(a, b, i);
		sc.close();
	}
public static void JjJuXie(String[] a, String[] b, int i) {
		int k, p, q, s = 0, flag = 1;
		for (p = 0; p < i; p++) {
			if (a[p].length() != b[p].length()) {
				if (a[p].length() > b[p].length()) {
					for (q = 0; q < b[p].length(); q++) {
						for (s = 0; s < a[p].length(); s++) {
							if ((b[p].charAt(q) == 155 - a[p].charAt(s))) {
								flag = 0;
								break;
							} else {
								flag = 1;
								continue;
							}
						}
					}
				} else {
					flag = 1;
				}

			} else {
				for (k = 0; k < a[p].length(); k++) {
					if (a[p].charAt(k) == 155 - b[p].charAt(k)) {
						flag = 0;// yes
					} else {
						flag = 1;// no
						break;
					}
				}

			}
			if (flag == 0) {
				System.out.println("YES");
			} else {
				System.out.println("NO");
			}
		}

	}

发表于 2016-08-21 00:11:21 回复(0)