[算法]字符串之变形词问题

2024-02-28 04:01| 来源: 网络整理| 查看: 265

一、判断两个字符串是否互为变形词：题目：

如果两个字符串中字符的种类相同并且每种字符出现的次数也相同，那么这两个字符串互为变形词。

解法一：

该方法适合只包含8位字符集的字符串，不适合包含中文的字符串比较。

思路：首先判断两个字符串的长度，如不同直接返回false;如果相同，则创建一个长度为256的整型数组，map[a]=b表示字符编码为a的字符出现了b次，遍历第一个字符串时，将对应字符对应的值加一，遍历另一个字符串时，将对应字符的值减一，（当然这两个过程既可以同时进行，也可以分先后进行），最后查看整型数组的每一项的值是否都为0，只要有一个不为零，则返回false，（或者判断是否有字符对应的值大于零，因为首先判断了两个字符串的长度是否相同，如果相同，而且两个字符串又不互为变形词，那么一定会出现第二个字符串的至少一种字符的个数大于第一个，此时该字符对应的值遍历后小于0。

public static boolean isAnagram(String str1, String str2) { if (str2 == null || str1 == null || str1.length() != str2.length()) { return false; } char[] c1 = str1.toCharArray(); char[] c2 = str2.toCharArray(); int[] map = new int[256]; //形式一： for (int i = 0; i < c1.length; i++) { map[c1[i]]++; } for (int i = 0; i < c2.length; i++) { if (map[c2[i]]-- == 0) return false; } /* 形式二： for (int i = 0; i < c1.length; i++) { map[c1[i]]++; map[c2[i]]--; } for (int i = 0; i < map.length; i++) { if (map[i] != 0) return false; }*/ return true; } 解法二：

借助于Arrays工具类：

首先排序，然后查看是否相等，在效率上不如解法一。

public boolean isAnagram(String s1, String s2) { if (s1 == null || s2 == null || s1.length() != s2.length()) { return false; } char[] ch1 = s1.toCharArray(); char[] ch2 = s2.toCharArray(); Arrays.sort(ch1); Arrays.sort(ch2); return Arrays.equals(ch1, ch2); } 解法三：

借助HashMap，原理与解法一基本相同，但是通用于Unicode字符。

public static boolean isAnagram(String s1,String s2){ if (s1==null||s2==null||s1.length()!=s2.length()) return false; char[] c1=s1.toCharArray(); char[] c2=s2.toCharArray(); Map map=new HashMap(); for (int i=0;i

【本文地址】

[算法]字符串之变形词问题

[算法]字符串之变形词问题

今日新闻

推荐新闻