题目描述:
电视剧《分界线》里面有一个片段,男主为了向警察透露案件细节,且不暴露自己,于是将报刊上的字剪切下来,剪拼成匿名信。
现在有一名举报人,希望借鉴这种手段,使用英文报刊完成举报操作。
但为了增加文章的混淆度,只需满足每个单词中字母数量一致即可,不关注每个字母的顺序。
解释:单词'on'允许通过单词'no'进行替代
报纸代表newspaper, 匿名信代表anonymousLetter, 求报纸内容是否可以拼成匿名信。
输入描述:
第一行输入newspaper内容,包括1-N个字符串,用空格分开
第二行输入anonymousLetter内容,包括1-N个字符串,用空格分开
1、newspaper和anonymousLetter的字符串由小写英文字母组成且每个字母只能使用一次
2、newspaper内容中的每个字符串字母顺序可以任意调整,但必须保证字符串的完整性(每个字符串不能有多余字母)
3、1<N<100 , 1<= newspaper.length, anonymousLetter.length <= 104
输出描述:
如果报纸可以拼成匿名信返回ture,否则返回false
补充说明:
收起
示例1
输入:
ab cd
ab
输出:
true
说明:
示例2
输入:
ab ef
aef
输出:
false
说明:
示例3
输入:
ab bcd ef
cbd fe
输出:
true
说明:
示例4
输入:
ab bcd ef
cd ef
输出:
false
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
public class Main {
private static boolean isValid(String[] newsWord, String[] letterWord) {
HashSet<String> set = new HashSet<>();
for (int i = 0; i < newsWord.length; i++) {
char[] wordChars = newsWord[i].toCharArray();
Arrays.sort(wordChars);
set.add(String.valueOf(wordChars));
}
for (int i = 0; i < letterWord.length; i++) {
char[] wordChars = letterWord[i].toCharArray();
Arrays.sort(wordChars);
if (!set.contains(String.valueOf(wordChars))) return false;
}
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String newspaper = sc.nextLine();
String anonymousLetter = sc.nextLine();
String[] newsWord = newspaper.split(" ");
String[] letterWord = anonymousLetter.split(" ");
System.out.println(isValid(newsWord,letterWord));
}
}
}
import sys
def divine():
# 读取第一行的n
b=[]
for i in range(2):
# 读取每一行
line = sys.stdin.readline().strip()
# 把每一行的数字分隔后转化成int列表
c=[]
d=[]
a = list(map(str, line.split()))
for j in range(len(a)):
for k in a[j]:
c.append(k)
c.sort()
d.append(c)
c=[]
b.append(d)
for i in range(len(b[1])):
if b[1][i] in b[0]:
b[0].remove(b[1][i])
else:
return('false')
return('true')
print (divine())
#include <iostream>
#include <cstdio>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
bool isSmaller(const int* a, const int* b) {
for (int i = 0; i < 26; i++) {
if (a[i] == b[i])
continue;
else
return (a[i] < b[i]);
}
return false;
}
bool isEqual(const int* a, const int* b) {
for (int i = 0; i < 26; i++) {
if (a[i] == b[i])
continue;
else
return false;
}
return true;
}
bool find(vector<int*> news, int* value, int len) {
int begin = 0;
int end = len;
int mid;
while (begin <= end) {
mid = (begin + end) / 2;
if (isSmaller(news[mid], value)) {
begin = mid + 1;
}
else
end = mid - 1;
}
if (begin < news.size() && isEqual(news[begin], value))
return true;
return false;
}
int main() {
string s;
int* tmp;
vector<int*> news;
while (cin >> s) {
tmp = new int[26];
for (int i = 0; i < 26; ++i)
tmp[i] = 0;
int slen = s.length();
for (int i = 0; i < slen; ++i) {
tmp[s[i] - 'a']++;
}
news.push_back(tmp);
if (cin.get() == '\n')
break;
}
sort(news.begin(), news.end(), isSmaller);
vector<int*> anoys;
while (cin >> s) {
tmp = new int[26];
for (int i = 0; i < 26; ++i)
tmp[i] = 0;
int slen = s.length();
for (int i = 0; i < slen; ++i) {
tmp[s[i] - 'a']++;
}
anoys.push_back(tmp);
if (cin.get() == '\n')
break;
}
int len = anoys.size();
bool flag = true;
for (int i = 0; i < len; i++) {
if (!find(news, anoys[i], news.size())) {
flag = false;
break;
}
}
if (flag)
cout << "true" << endl;
else
cout << "false" << endl;
}