(A卷,100分)- 匿名信（Java & JS & Python）

题目描述

电视剧《分界线》里面有一个片段，男主为了向警察透露案件细节，且不暴露自己，于是将报刊上的字减下来，剪拼成匿名信。
现在又一名举报人，希望借鉴这种手段，使用英文报刊完成举报操作。
但为了增加文章的混淆度，只需满足每个单词中字母数量一致即可，不关注每个字母的顺序。
解释：单词on允许通过单词no进行替代。
报纸代表newspaper，匿名信代表anonymousLetter，求报纸内容是否可以拼成匿名信。

输入描述

第一行输入newspaper内容，包括1-N个字符串，用空格分开
第二行输入anonymousLetter内容，包括1-N个字符串，用空格分开。

newspaper和anonymousLetter的字符串由小写英文字母组成，且每个字母只能使用一次；
newspaper内容中的每个字符串字母顺序可以任意调整，但必须保证字符串的完整性（每个字符串不能有多余字母）
1 < N < 100,
1 <= newspaper.length,anonymousLetter.length <= 10^4

输出描述

如果报纸可以拼成匿名信返回true，否则返回false

用例

题目解析

用例1的意思是：

报纸上有两个单词：ab、cd，而要写的匿名信需要一个单词ab，因此可以直接使用报纸上的单词ab，所以可以写出匿名信。

用例2的意思是：

报纸上有两个单词：ab、ef，而要写的匿名信需要一个aef，根据题目意思

只需满足每个单词中字母数量一致即可

如果想用报纸上的单词，代替匿名信上的单词，则这两个单词的字母数量必须一致。

因此，对于匿名信单词aef，有三个字母，而报纸上没有有三个字母的单词，因此输出false。

我增加一个自测用例，说明下面这个特点

不关注每个字母的顺序。单词on允许通过单词no进行替代。

比如，报纸单词ba、cd，匿名信需要单词ab，而题目说

不关注每个字母的顺序

因此匿名信的单词ab可以用报纸的单词ba代替，因此输出true。

本题需要关注下数量级：1 <= newspaper.length,anonymousLetter.length <= 10^4

因此双重for的O(n^2)时间复杂度会高达一亿次循环，会超时。

我的策略如下，统计出newspaper中每个单词出现的次数到count对象中，统计前，对每个单词进行字典序排序，这样就可以忽略字母顺序了。

比如，用例1的newspaper会统计出count: { "ab":1, "cd": 1}，这个时间复杂度是O(n)

然后，再遍历anonymousLetter每个单词，并对单词进行字典序排序，忽略字母顺序，然后用排序后单词去count中找，如果count[letter] > 0，则可以找到，然后count[letter]–

遵循题目意思：每个字母只能使用一次

如果count[letter]不存在，或者count[letter]===0，则说明匿名信中的某个单词在报纸单词中找不到替代，因此可以直接返回false。

如果全部都可以找到，则返回true。

这个过程的时间复杂度是O(n)。

因此总的时间复杂度是O(n)。

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 2) {
    const newspaper = lines[0].split(" ");
    const anonymousLetter = lines[1].split(" ");
    console.log(getResult(newspaper, anonymousLetter));

    lines.length = 0;
  }
});

function getResult(newspaper, anonymousLetter) {
  const count = {};
  for (let str of newspaper) {
    str = [...str].sort().join("");
    count[str] ? count[str]++ : (count[str] = 1);
  }

  let flag = true;
  for (let str of anonymousLetter) {
    str = [...str].sort().join("");
    if (count[str] > 0) {
      count[str]--;
    } else {
      flag = false;
      break;
    }
  }

  return flag;
}

Java算法源码

import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    String[] newspaper = sc.nextLine().split(" ");
    String[] anonymousLetter = sc.nextLine().split(" ");

    System.out.println(getResult(newspaper, anonymousLetter));
  }

  public static boolean getResult(String[] newspaper, String[] anonymousLetter) {
    HashMap<String, Integer> count = new HashMap<>();
    for (String str : newspaper) {
      String newStr = strSort(str);
      count.put(newStr, count.getOrDefault(newStr, 0) + 1);
    }

    boolean flag = true;
    for (String str : anonymousLetter) {
      String newStr = strSort(str);

      if (count.containsKey(newStr) && count.get(newStr) > 0) {
        count.put(newStr, count.get(newStr) - 1);
      } else {
        flag = false;
        break;
      }
    }

    return flag;
  }

  public static String strSort(String str) {
    char[] cArr = str.toCharArray();
    Arrays.sort(cArr);
    return new String(cArr);
  }
}

Python算法源码

# 输入获取
newspaper = input().split()
anonymousLetter = input().split()


# 算法源码
def getResult(newspaper, anonymousLetter):
    count = {}
    for s in newspaper:
        s = "".join(sorted(s))
        if count.get(s) is None:
            count[s] = 1
        else:
            count[s] += 1

    flag = True
    for s in anonymousLetter:
        s = "".join(sorted(s))
        if count.get(s) is not None and count[s] > 0:
            count[s] -= 1
        else:
            flag = False
            break

    return str(flag).lower()


# 调用算法
print(getResult(newspaper, anonymousLetter))