你将得到一个字符串数组 A。
如果经过任意次数的移动,S == T,那么两个字符串 S 和 T 是特殊等价的。
一次移动包括选择两个索引 i 和 j,且 i % 2 == j % 2,交换 S[j] 和 S [i]。
现在规定,A 中的特殊等价字符串组是 A 的非空子集 S,这样不在 S 中的任何字符串与 S 中的任何字符串都不是特殊等价的。
返回 A 中特殊等价字符串组的数量。
示例 1:
输入:["a","b","c","a","c","c"]
输出:3
解释:3组 ["a","a"],["b"],["c","c","c"]
示例 2:
输入:["aa","bb","ab","ba"]
输出:4
解释:4 组 ["aa"],["bb"],["ab"],["ba"]
示例 3:
输入:["abc","acb","bac","bca","cab","cba"]
输出:3
解释:3 组 ["abc","cba"],["acb","bca"],["bac","cab"]
示例 4:
输入:["abcd","cdab","adcb","cbad"]
输出:1
解释:1 组 ["abcd","cdab","adcb","cbad"]
提示:
实际上特殊等价字符串数组的根本就是,每一个字符串中所有的奇数位置的字母排序后,以及所有偶数位置的字母排序后,均相同,所有采用奇偶分离排序后再结合比较即可即可,在这里我用到的是通过HashSet进行相同覆盖的操作,话不多说,直接上代码。
/** * * @version: 1.1.0 * @Description: 特殊等价字符串组test * @author: wsq * @date: 2020年6月7日下午9:00:24 */ @SuppressWarnings("all") public class FirstProblem { public static void main(String[] args) { // 获取用户输入的集合 List<String> inputList = getInputList(); // 获取结果 int count = getResultList(inputList); System.err.println("The count is:" + count); } /** * * @Description: 获取用户输入的集合 * @author: wsq * @date: 2020年6月7日下午9:00:24 */ public static List<String> getInputList() { List<String> inputList = new ArrayList<String>(); int stringSize = 0; while (true) { // 输入每一个字符串的长度 System.out.println("Please input the length of each string"); stringSize = new Scanner(System.in).nextInt(); if (stringSize < 20) { break; } // 长度不可以超过20 System.out.println("Please input again,the length of the string cannot exceed 20"); } while (true) { // 数组总长度不可以超过1000 if (inputList.size() == 1000) { System.out.println("The length is exceed 1000,you can‘t input anything"); break; } System.out.println("Please input string"); String value = new Scanner(System.in).nextLine(); // 每个字符串长度必须相同 if (value.length() != stringSize) { System.out.println("Please input again,the string length must be 20" + stringSize); continue; } // 字符串必须都为小写字母 if (!isLetterDigit(value)) { System.out.println("Please input again,string must consist of lowercase letters"); continue; } inputList.add(value); // 输入N退出循环,停止输入 System.out.println("Input anything to go on or input ‘N‘ to leave"); String button = new Scanner(System.in).nextLine(); if (button.equals("N")) { break; } } return inputList; } /** * * @Description: 获取最终的结果 * @author: wsq * @date: 2020年6月7日下午9:00:24 */ public static int getResultList(List<String> inputList) { // 用户存储处理过的数据(去重) Set<String> changeList = new HashSet<String>(); for (int index = 0; index < inputList.size(); index++) { // 用来放奇数 List<Character> oddList = new ArrayList<Character>(); // 用来放偶数 List<Character> evenList = new ArrayList<Character>(); String input = inputList.get(index); char[] array = input.toCharArray(); // 奇偶分离 for (int i = 0; i < array.length; i++) { if (i % 2 != 0) { oddList.add(array[i]); } else { evenList.add(array[i]); } } // 分别排序 Collections.sort(oddList); Collections.sort(evenList); // 集合合并 oddList.addAll(evenList); // 转化为字符串 String change = oddList.stream().map(String::valueOf).collect(Collectors.joining(",")); changeList.add(change); } return changeList.size(); } /** * * @Description: 正则表达式(只能为小写字母) * @author: wsq * @date: 2020年6月7日下午9:00:24 */ public static boolean isLetterDigit(String str) { String regex = "^[a-z]+$"; return str.matches(regex); }
如果业界大佬有更方便的方法,或者别的思路,本人欢迎批评指教!
原文:https://www.cnblogs.com/mcjhcnblogs/p/13062674.html