全网最全面的华为OD机试真题汇总,100%原题题库,不需要开会员即可查看全部内容,更多考题请查看真题库。
真题库:https://www.yuque.com/codernav.com/od
题目:寻找相似单词
知识点字符串排序
时间限制:1s 空间限制:256MB 限定语言:不限
题目描述:
给定一个可存储若干单词的字典,找出指定单词的所有相似单词,并且按照单词名称从小到大排序输出。单词仅包括字母,但可能大小写并存(大写不一定只出现在首字母)。
相似单词说明:给定一个单词X,如果通过任意交换单词中字母的位置得到不同的单词Y,那么定义Y是X的相似单词,如abc、bca即为相似单词(大小写是不同的字母,如a和A算两个不同字母)。
字典序排序: 大写字母<小写字母。同样大小写的字母,遵循26字母顺序大小关系。即A<B<C<…<X<Y<Z<a<b<c<…<x<y<z. 如Bac<aBc<acB<cBa.
输入描述:
第一行为给定的单词个数N(N为非负整数)
从第二行到地N+1行是具体的单词(每行一个单词)
最后一行是指定的待检测单词(用于检测上面给定的单词中哪些是与该指定单词是相似单词,该单词可以不是上面给定的单词)
输出描述:
从给定的单词组中,找出指定单词的相似单词,并且按照从小到大字典序排列输出,中间以空格隔开
如果不存在,则输出null(字符串null)
示例1
输入:
4
abc
dasd
tad
bca
abc
输出:
abc bca
说明:
在给定的输入中,与abc是兄弟单词的是abc bca,且输出按照字典序大小排序,输出的所有单词以空格隔开
示例2
输入:
4
abc
dasd
tad
bca
abd
输出:
null
说明:
给定单词组中,没有与给定单词abd是兄弟单词,输出为null(字符串null)
解题思路:
判断两个字符串是否相似的方法:
将两个字符串转换为字符数组,排序后比较各位置的字符是否都相同,如若都相同则相似,只要有一个不相同则不相似。
代码实现一:
package com.codernav.demo.hwod.exam; import java.util.*; /** * @title 寻找相似单词 * @Description 给定一个可存储若干单词的字典,找出指定单词的所有相似单词,并且按照单词名称从小到大排序输出。 * 单词仅包括字母,但可能大小写并存(大写不一定只出现在首字母)。 * 相似单词说明:给定一个单词X,如果通过任意交换单词中字母的位置得到不同的单词Y,那么定义Y是X的相似单词, * 如abc、bca即为相似单词(大小写是不同的字母,如a和A算两个不同字母)。 * 字典序排序: 大写字母<小写字母。同样大小写的字母,遵循26字母顺序大小关系。 * 即A<B<C<...<X<Y<Z<a<b<c<...<x<y<z. 如Bac<aBc<acB<cBa. * @Author 开发者导航 * @website https://codernav.com * @date 2023/5/28 */ public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); sc.nextLine(); List<String> list = new ArrayList<>(); for (int i = 0; i < N; i++) { list.add(sc.nextLine()); } String X = sc.nextLine(); Collections.sort(list); String res = ""; for (String Y : list) { if (Y.length() == X.length() && isSimilar(X, Y)) { //长度相同才能相似 res += Y + " "; } } System.out.println(res.length() == 0 ? "null" : res.substring(0, res.length() - 1)); } /** * 将两个字符串转换为字符数组 * 排序后比较字符是否都相同 * 都相同则相似 * 有一个不相同则不相似 * * @param X * @param Y * @return */ public static boolean isSimilar(String X, String Y) { char[] charX = X.toCharArray(); char[] charY = Y.toCharArray(); Arrays.sort(charX); Arrays.sort(charY); boolean res = true; for (int i = 0; i < charX.length; i++) { if (charX[i] != charY[i]) { //有一个字符不相同就不相似 res = false; break; } } return res; } }
代码实现二:Java代码满分实现
package com.codernav.demo.hwod.exam; import java.util.Arrays; import java.util.Scanner; import java.util.TreeSet; /** * @title 寻找相似单词 * @Description 给定一个可存储若干单词的字典,找出指定单词的所有相似单词,并且按照单词名称从小到大排序输出。 * 单词仅包括字母,但可能大小写并存(大写不一定只出现在首字母)。 * 相似单词说明:给定一个单词X,如果通过任意交换单词中字母的位置得到不同的单词Y,那么定义Y是X的相似单词, * 如abc、bca即为相似单词(大小写是不同的字母,如a和A算两个不同字母)。 * 字典序排序: 大写字母<小写字母。同样大小写的字母,遵循26字母顺序大小关系。 * 即A<B<C<...<X<Y<Z<a<b<c<...<x<y<z. 如Bac<aBc<acB<cBa. * @Author 开发者导航 * @website https://codernav.com * @date 2023/5/28 */ public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); String[] str = new String[n]; String s; for (int i = 0; i < n; i++) { str[i] = in.next(); } s = in.next(); TreeSet<String> set = new TreeSet<>(); for (String value : str) { if (isXiangShi(s, value)) { set.add(value); } } if (set.size() == 0) { System.out.println("null"); } else { for (String c : set) { System.out.print(c + " "); } } } public static boolean isXiangShi(String a, String b) { if (a.length() != b.length()) { return false; } char[] s1 = a.toCharArray(); char[] s2 = b.toCharArray(); Arrays.sort(s1); Arrays.sort(s2); for (int i = 0; i < s1.length; i++) { if (s1[i] != s2[i]) { return false; } } return true; } }