(A卷,100分)- 真正的密码（Java & JS & Python）

题目描述

在一行中输入一个字符串数组，如果其中一个字符串的所有以索引0开头的子串在数组中都有，那么这个字符串就是潜在密码，

在所有潜在密码中最长的是真正的密码，如果有多个长度相同的真正的密码，那么取字典序最大的为唯一的真正的密码，求唯一的真正的密码。

输入描述

无

输出描述

无

用例

题目解析

我的解题思路如下：

将输入的所有字符串先按照长度升序，如果长度相同，则按照字典序升序。

这样最后一个字符串必然就是长度最长，字典序最大的，我们从最后一个字符串str开始：

接下来，我们不停地截取str的子串，即如下闭区间的子串：

0~str.length-2

0~str.length-3

0~str.length-4

….

0~2

0~1

0~0

然后将在输入的所有字符串中查找每次截取的子串是否存在，如果多存在则返回当str作为题解，如果有一个不存在，则直接中断查找，开始下一个str

JavaScript算法源码

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

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

rl.on("line", (line) => {
  const arr = line.split(" ");

  console.log(getResult(arr));
});

function getResult(arr) {
  const set = new Set(arr);
  arr.sort((a, b) =>
    a.length != b.length ? a.length - b.length : a == b ? 0 : a > b ? 1 : -1
  );

  outer: for (let i = arr.length - 1; i >= 0; i--) {
    const str = arr[i];

    for (let j = str.length - 1; j >= 1; j--) {
      if (!set.has(str.slice(0, j))) continue outer;
    }

    return str;
  }
}

Java算法源码

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

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

    String[] arr = sc.nextLine().split(" ");
    System.out.println(getResult(arr));
  }

  public static String getResult(String[] arr) {
    HashSet<String> set = new HashSet<>(Arrays.asList(arr));

    Arrays.sort(arr, (a, b) -> a.length() != b.length() ? a.length() - b.length() : a.compareTo(b));

    outer:
    for (int i = arr.length - 1; i >= 0; i--) {
      String str = arr[i];

      for (int j = str.length() - 1; j >= 1; j--) {
        if (!set.contains(str.substring(0, j))) continue outer;
      }

      return str;
    }

    return "";
  }
}

Python算法源码

# 输入获取
arr = input().split()


# 算法入口
def getResult(arr):
    setArr = set(arr)

    arr.sort(key=lambda s: (len(s), [ord(c) for c in s]))

    for i in range(len(arr) - 1, -1, -1):
        s = arr[i]
        flag = True

        for j in range(len(s) - 1, 0, -1):
            if s[:j] not in setArr:
                flag = False
                break

        if flag:
            return s

    return ""


# 算法调用
print(getResult(arr))