我编写了一个Java程序来查找2个字符串的Anagram。
供参考:如果两个字符串使用完全相同的字母书写,忽略空格,标点符号和大小写,则两个字符串是字谜。每个字母在两个字符串中应该具有相同的计数。例如,陆军和玛丽是彼此的字谜。
程序:
package practice;
import java.util.ArrayList;
import java.util.List;
public class Anagram_String {
public static void main(String[] args) {
String s1="mary";
String s2="army";
int k=0;
List<String> matchedChar= new ArrayList<String>();
String charmatch="";
char[] ch1= s1.toLowerCase().toCharArray();
char[] ch2= s2.toLowerCase().toCharArray();
if(s1.length()==s2.length())
{
for(int i=0;i<s1.length();i++)
{
for(int j=0;j<s2.length();j++)
{
if(ch1[i]==ch2[j])
{
k++;
charmatch=String.valueOf(ch1[i]);
System.out.println(charmatch);
matchedChar.add(charmatch);
System.out.println("Arraylist value is "+matchedChar.toString());
System.out.println(matchedChar.size());
}
}
k=0;
}
String arrayValue=matchedChar.toString();
System.out.println("Array value is "+arrayValue);
if(arrayValue.contains(s2)){
System.out.println("String 1 and String 2 are anagrams of each other");
}
else
{
System.out.println("String 1 and String 2 are not anagrams of each other");
}
}
}
}
输出:
m
Arraylist value is [m]
1
a
Arraylist value is [m, a]
2
r
Arraylist value is [m, a, r]
3
y
Arraylist value is [m, a, r, y]
4
Array value is [m, a, r, y]
String 1 and String 2 are not anagrams of each other
在这里,如果您看到所有字符都添加到arraylist但与字符串比较时,它显示输出,因为它们不是彼此的字谜。
请帮我找到解决方案。
谢谢,
我认为你的解决方案只适用于具有独特字符的单词,时间复杂度为O(n ^ 2)(其中n - 是String的长度)。
但是,对于这样的问题有更好的解决方案:
String.toCharArray()
值您可以计算两个字符串中的字母数。如果两个字符串具有相同数量的字母,则它们是字谜。
您可以使用int[]
来存储字母数。
public static boolean anagrams(String a, String b) {
int[] letters = new int[26];
// Convert to upper case because the test is case insensitive
a = a.toUpperCase();
b = b.toUpperCase();
for (int i = 0; i < a.length(); i++) {
char ch = a.charAt(i);
if (ch < 'A' || ch > 'Z') {
continue; // Skip non letters
}
letters[ch - 'A']++; // Increment number of the current letter
}
for (int i = 0; i < b.length(); i++) {
char ch = b.charAt(i);
if (ch < 'A' || ch > 'Z') {
continue; // Skip non letters
}
letters[ch - 'A']--; // Decrement number of the current letter
}
for (int i = 0; i < letters.length; i++) {
if (letters[i] != 0) {
// If there are more or less of this letter
// in the first string it is not an anagram
return false;
}
}
return true;
}
注意,该算法在O(n)中完成,其中n是每个字符串的字母数。对字符串进行排序至少需要O(n log(n))
从AxelH的评论中得出这个想法,可以创建一个外部方法循环如下。
private void countLetters(int[] letters, String str, int incrementFactor) {
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
if (ch < 'A' || ch > 'Z') {
continue; // Skip non letters
}
letters[ch - 'A'] += incrementFactor;
}
}
public static boolean anagrams(String a, String b) {
int[] letters = new int[26];
countLetters(letters, a.toUpperCase(), 1); // Note the +1
countLetters(letters, b.toUpperCase(), -1); // Note the -1
for (int i = 0; i < letters.length; i++) {
if (letters[i] != 0) {
// If there are more or less of this letter
// in the first string it is not an anagram
return false;
}
}
return true;
}
在我看来,这是一种更加可读和优雅的方式。谢谢AxelH。
注意在前面的代码中有像letters[ch - 'A']++
这样的表达式。这行代码使用了类型为char
的有趣属性,这是一种特殊的原始数字类型,因此可以对其使用数学运算。
特别是:
'A' - 'A' --> 0
'B' - 'A' --> 1
'C' - 'A' --> 2
'D' - 'A' --> 3
...
'Z' - 'A' --> 25
所以这个表达式可以用来给一个字母索引,从一个字母开始,从0开始,A结尾为25,Z为Z.
你的输出本身就是这样的:数组值是[m,a,r,y]
如上所述,我也只是创建数组并对它们进行排序,但这里是您可能正在搜索的解决方案:
String s1="mary";
String s2="army";
List<String> matchedChar= new ArrayList<String>();
String charmatch="";
char[] ch1= s1.toLowerCase().toCharArray();
char[] ch2= s2.toLowerCase().toCharArray();
if(s1.length()==s2.length())
{
for(int i=0;i<s1.length();i++)
{
for(int j=0;j<s2.length();j++)
{
if(ch1[i]==ch2[j])
{
charmatch=String.valueOf(ch1[i]);
System.out.println(charmatch);
matchedChar.add(charmatch);
System.out.println("Arraylist value is "+matchedChar.toString());
System.out.println(matchedChar.size());
}
}
}
String arrayValue="";
for (String s : matchedChar){
arrayValue = arrayValue + s;
}
System.out.println("Array value is "+arrayValue);
System.out.println("s1 value is "+s1);
if(arrayValue.equals(s1)){
System.out.println("String 1 and String 2 are anagrams of each other");
}
else
{
System.out.println("String 1 and String 2 are not anagrams of each other");
}
}
我的回答与Marine的非常类似,但是对Java 8流采用了一些更高级的方法,使代码更简洁和可读:
public class Application {
public boolean isAnagramsEqual(String str1, String str2) {
Map<Character, Long> count = countChars(str1);
Map<Character, Long> count2 = countChars(str2);
return count.equals(count2);
}
private Map<Character, Long> countChars(String str) {
return str.toLowerCase()
.chars().mapToObj(ch -> (char) ch) //convert into stream of Characters
.filter(Character::isLetterOrDigit) //filter out not-needed chars
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
}}
方法countChars
创建一个映射,每个唯一字符映射到给定字符串中的计数。它可能比海军陆战队员的表现要差一点,但它仍然是O(n)
。
在String上使用.split(“(?!^)”)使其成为一个String数组。接下来排序数组并进行比较。这对我来说也是最好的选择。
这是通过排序数组来实现的:
public static void main(String[] args) {
System.out.println(isAnagram("mary", "army"));
}
public static boolean isAnagram(String s1, String s2){
char[] c1 = s1.toLowerCase().toCharArray();
char[] c2 = s2.toLowerCase().toCharArray();
Arrays.sort(c1);
Arrays.sort(c2);
boolean anagram = false;
if(Arrays.equals(c1, c2)){anagram = true;}
return anagram;
}
在这段代码中,我使用代码:String.toCharArray()
将我的字符串转换为char数组,该函数名为toSort(),并对字符串中的单词进行排序。然后在Isanagram()方法里面我检查它是否是字谜。为此,我必须确定在将一个字符串中的每个字符与其他字符串进行比较后,排序的字符串是否具有相同的长度。这是完整的代码尝试分解每个方法和研究。
import java.util.Scanner;
public class StANaEx1 {
String toSort(String s5){
int i,j;
char temp;
char ch1[] = s5.toCharArray();
int len = ch1.length;
for(i=0;i<len;i++){
for(j=i+1;j<len;j++){
if(ch1[i]>ch1[j]){
temp = ch1[i];
ch1[i] = ch1[j];
ch1[j] = temp;
}
}
}
String s6 = new String(ch1);
return s6;
}
void isAnagram(String s9,String s10){
int i,len1,len2,flag=0;
System.out.println("s9 : "+s9);
System.out.println("s10 : "+s10);
System.out.println("");
s9 = s9.trim(); //To remove white spaces again no need.I used because my compiler didn't recognize my replace() method in main() method.
s10 = s10.trim();
len1 = s9.length();
len2 = s10.length();
System.out.println("len1 : "+len1); //To check the length of the given strings without white spaces.
System.out.println("len2 : "+len2);
System.out.println("");
for(i=0;i<len1;i++){
System.out.println("s9["+i+"] : "+s9.charAt(i)); //Error checking.
}
System.out.println("");
for(i=0;i<len2;i++){
System.out.println("s10["+i+"] : "+s10.charAt(i));
}
System.out.println("");
if(len1!=len2){
System.out.println("Not Anagram string length different");
}
else{
for(i=0;i<len1;i++){ //Since string lengths are same len1 = len2.
if(s9.charAt(i)!=s10.charAt(i)){
flag=1;
break;
}
}
if(flag==0){
System.out.println("Anagram");
}
else{
System.out.println("Not Anagram");
}
}
}
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
StANaEx1 ob1 = new StANaEx1();
System.out.println("-----Anagram checking-----");
System.out.println("");
System.out.println("Enter the 1st String: ");
System.out.println("");
String s1 = sc.nextLine();
s1 = s1.replace("//s", ""); //This is to remove white spaces.
String s3 = s1.toLowerCase(); //Change the input string to lower case in order to make sorting easy.
System.out.println("");
System.out.println("Enter the next String: ");
String s2 = sc.nextLine();
s2 = s2.replace("//s", "");
String s4 = s2.toLowerCase();
System.out.println("");
String s7 = ob1.toSort(s3);
String s8 = ob1.toSort(s4);
ob1.isAnagram(s7,s8);
sc.close();
}
}
产量
-----Anagram checking-----
Enter the 1st String:
Mary
Enter the next String:
army
s9 : amry
s10 : amry
len1 : 4
len2 : 4
s9[0] : a
s9[1] : m
s9[2] : r
s9[3] : y
s10[0] : a
s10[1] : m
s10[2] : r
s10[3] : y
Anagram
输出2
-----Anagram checking-----
Enter the 1st String:
Sniper
Enter the next String:
kill
s9 : einprs
s10 : ikll
len1 : 6
len2 : 4
s9[0] : e
s9[1] : i
s9[2] : n
s9[3] : p
s9[4] : r
s9[5] : s
s10[0] : i
s10[1] : k
s10[2] : l
s10[3] : l
Not Anagram string length different