使用 basic Java 检查两个字符串是否是彼此的变位词
Checking if two Strings are anagram of each other using basic Java
我正在 java Netbeans 中编写以下代码,它对普通的字谜非常有用。但是如果两个文本字段包含包含重复字母的单词,那么代码将无法工作。可能是什么问题,我该如何解决?我对 Java 很基础,还不能理解数组。
String s1= t1.getText();
String s2= t2.getText();
int b=0,c=0;
if(s1.length()!=s2.length())
System.out.print("No");
else {
for(int i=0;i<s1.length();i++) {
char s = s1.charAt(i);
for(int j=0;j<s2.length();j++) {
if(s==s2.charAt(j)){
b++;
}
}
if(b==0)
break;
}
if(b==0)
System.out.print("No");
else
System.out.print("YES");
}
System.out.print(b);
我会选择更简单的推理方式:如果两个字符串在排序后完全匹配,则它们就是变位词。
所以在 Java 中它会是这样的:
String s1 = "cat";
String s2 = "tac";
boolean isAnagram = false;
if (s1.length() == s2.length()) {
char[] s1AsChar = s1.toCharArray();
char[] s2AsChar = s2.toCharArray();
Arrays.sort(s1AsChar);
Arrays.sort(s2AsChar);
isAnagram = Arrays.equals(s1AsChar, s2AsChar);
}
您想比较排序后的字符。这是一条线:
return Arrays.equals(s1.chars().sorted().toArray(),
s2.chars().sorted().toArray());
Arrays.equals()
为您比较长度和所有元素。
由于您似乎是初学者,这里有一个不涉及其他 类 或流的函数的解决方案。它只涉及数组的使用以及 char
也可以表示 int
.
的事实
public static void main(String[] args) throws ParseException {
String s1= "anagram";
String s2= "margana";
// We make use of the fact that a char does also represent an int.
int lettersS1[] = new int[Character.MAX_VALUE];
int lettersS2[] = new int[Character.MAX_VALUE];
if(s1.length()!=s2.length())
System.out.print("No");
else {
// Loop through the String once
for(int i = 0; i<s1.length() ;++i) {
// we can just use the char value as an index
// and increase the value of it. This is our identifier how often
// each letter was aviable in the String. Alse case insensitive right now
lettersS1[s1.toLowerCase().charAt(i)]++;
lettersS2[s2.toLowerCase().charAt(i)]++;
}
// set a flag if the Strings were anagrams
boolean anag = true;
// We stop the loop as soon as we noticed they are not anagrams
for(int i = 0;i<lettersS1.length&&anag;++i) {
if(lettersS1[i] != lettersS2[i]) {
// If the values differ they are not anagrams.
anag = false;
}
}
// Depending on the former loop we know if these two strings are anagrams
if(anag) {
System.out.print("Anagram");
} else {
System.out.print("No anagram");
}
}
}
这是我的解决方案,我们计算第一个字符串中每个字符的出现次数,然后从第二个字符串中的计数中减去它。最后,检查字符数是否不为0则这两个字符串不是变位词。
public static boolean isAnagram(String a, String b){
//assume that we are using ASCII
int[] charCnt = new int[256];
for(int i = 0; i < a.length(); i++){
charCnt[a.charAt(i)]++;
}
for(int i = 0; i< b.length(); i++){
charCnt[b.charAt(i)]--;
}
for(int i = 0; i<charCnt.length; i++){
if(charCnt[i] != 0) return false;
}
return true;
}
另一种解决方案,基于出现计数器:
static boolean areAnagrams(CharSequence a, CharSequence b) {
int len = a.length();
if (len != b.length())
return false;
// collect char occurrences in "a"
Map<Character, Integer> occurrences = new HashMap<>(64);
for (int i = 0; i < len; i++)
occurrences.merge(a.charAt(i), 1, Integer::sum);
// for each char in "b", look for matching occurrence
for (int i = 0; i < len; i++) {
char c = b.charAt(i);
int cc = occurrences.getOrDefault(c, 0);
if (cc == 0)
return false;
occurrences.put(c, cc - 1);
}
return true;
}
尽管此解决方案不如 "sort-and-compare" 优雅,但它可能对长字符串更有效,因为它在 O(n) 而不是 O(n logn) 和 returns 一旦在第二个字符串的某个位置找不到匹配项。
走出 "Basic Java" 领域,我修改了算法以处理 surrogate pairs。这里收集匹配的不是char
,而是int
个codepoints:
static boolean areAnagrams(CharSequence a, CharSequence b) {
int len = a.length();
if (len != b.length())
return false;
// collect codepoint occurrences in "a"
Map<Integer, Integer> ocr = new HashMap<>(64);
a.codePoints().forEach(c -> ocr.merge(c, 1, Integer::sum));
// for each codepoint in "b", look for matching occurrence
for (int i = 0, c = 0; i < len; i += Character.charCount(c)) {
int cc = ocr.getOrDefault((c = Character.codePointAt(b, i)), 0);
if (cc == 0)
return false;
ocr.put(c, cc - 1);
}
return true;
}
我正在 java Netbeans 中编写以下代码,它对普通的字谜非常有用。但是如果两个文本字段包含包含重复字母的单词,那么代码将无法工作。可能是什么问题,我该如何解决?我对 Java 很基础,还不能理解数组。
String s1= t1.getText();
String s2= t2.getText();
int b=0,c=0;
if(s1.length()!=s2.length())
System.out.print("No");
else {
for(int i=0;i<s1.length();i++) {
char s = s1.charAt(i);
for(int j=0;j<s2.length();j++) {
if(s==s2.charAt(j)){
b++;
}
}
if(b==0)
break;
}
if(b==0)
System.out.print("No");
else
System.out.print("YES");
}
System.out.print(b);
我会选择更简单的推理方式:如果两个字符串在排序后完全匹配,则它们就是变位词。 所以在 Java 中它会是这样的:
String s1 = "cat";
String s2 = "tac";
boolean isAnagram = false;
if (s1.length() == s2.length()) {
char[] s1AsChar = s1.toCharArray();
char[] s2AsChar = s2.toCharArray();
Arrays.sort(s1AsChar);
Arrays.sort(s2AsChar);
isAnagram = Arrays.equals(s1AsChar, s2AsChar);
}
您想比较排序后的字符。这是一条线:
return Arrays.equals(s1.chars().sorted().toArray(),
s2.chars().sorted().toArray());
Arrays.equals()
为您比较长度和所有元素。
由于您似乎是初学者,这里有一个不涉及其他 类 或流的函数的解决方案。它只涉及数组的使用以及 char
也可以表示 int
.
public static void main(String[] args) throws ParseException {
String s1= "anagram";
String s2= "margana";
// We make use of the fact that a char does also represent an int.
int lettersS1[] = new int[Character.MAX_VALUE];
int lettersS2[] = new int[Character.MAX_VALUE];
if(s1.length()!=s2.length())
System.out.print("No");
else {
// Loop through the String once
for(int i = 0; i<s1.length() ;++i) {
// we can just use the char value as an index
// and increase the value of it. This is our identifier how often
// each letter was aviable in the String. Alse case insensitive right now
lettersS1[s1.toLowerCase().charAt(i)]++;
lettersS2[s2.toLowerCase().charAt(i)]++;
}
// set a flag if the Strings were anagrams
boolean anag = true;
// We stop the loop as soon as we noticed they are not anagrams
for(int i = 0;i<lettersS1.length&&anag;++i) {
if(lettersS1[i] != lettersS2[i]) {
// If the values differ they are not anagrams.
anag = false;
}
}
// Depending on the former loop we know if these two strings are anagrams
if(anag) {
System.out.print("Anagram");
} else {
System.out.print("No anagram");
}
}
}
这是我的解决方案,我们计算第一个字符串中每个字符的出现次数,然后从第二个字符串中的计数中减去它。最后,检查字符数是否不为0则这两个字符串不是变位词。
public static boolean isAnagram(String a, String b){
//assume that we are using ASCII
int[] charCnt = new int[256];
for(int i = 0; i < a.length(); i++){
charCnt[a.charAt(i)]++;
}
for(int i = 0; i< b.length(); i++){
charCnt[b.charAt(i)]--;
}
for(int i = 0; i<charCnt.length; i++){
if(charCnt[i] != 0) return false;
}
return true;
}
另一种解决方案,基于出现计数器:
static boolean areAnagrams(CharSequence a, CharSequence b) {
int len = a.length();
if (len != b.length())
return false;
// collect char occurrences in "a"
Map<Character, Integer> occurrences = new HashMap<>(64);
for (int i = 0; i < len; i++)
occurrences.merge(a.charAt(i), 1, Integer::sum);
// for each char in "b", look for matching occurrence
for (int i = 0; i < len; i++) {
char c = b.charAt(i);
int cc = occurrences.getOrDefault(c, 0);
if (cc == 0)
return false;
occurrences.put(c, cc - 1);
}
return true;
}
尽管此解决方案不如 "sort-and-compare" 优雅,但它可能对长字符串更有效,因为它在 O(n) 而不是 O(n logn) 和 returns 一旦在第二个字符串的某个位置找不到匹配项。
走出 "Basic Java" 领域,我修改了算法以处理 surrogate pairs。这里收集匹配的不是char
,而是int
个codepoints:
static boolean areAnagrams(CharSequence a, CharSequence b) {
int len = a.length();
if (len != b.length())
return false;
// collect codepoint occurrences in "a"
Map<Integer, Integer> ocr = new HashMap<>(64);
a.codePoints().forEach(c -> ocr.merge(c, 1, Integer::sum));
// for each codepoint in "b", look for matching occurrence
for (int i = 0, c = 0; i < len; i += Character.charCount(c)) {
int cc = ocr.getOrDefault((c = Character.codePointAt(b, i)), 0);
if (cc == 0)
return false;
ocr.put(c, cc - 1);
}
return true;
}