Java程序检查字符串是否是变位词

19-02-21 jdon
         

字符串变位词检查:有多种方法来查找两个字符串是变位词还是非变位词。经典的方法是获取每个字符串的字符数组,然后比较它们,如果两个字符数组都相等,那么字符串就是变位词。但在进行比较之前,请确保两个字符串的大小写相同(例如小写或大写),并且对字符数组进行排序,因为equals数组方法,只有当数组包含相同的长度,并且每个索引具有相同的字符时才返回true。

为了简单起见,我省略了检查字符串是否为空,并将其转换为大写或小写,如果需要,可以执行此操作。如果面试官要求你写生产质量代码,那么我建议你一定要做这些检查,并为空字符串抛出IllegalArgumentException,否则你只需返回false。我个人更喜欢返回false而不是抛出异常,类似于equals()方法。不管怎样,这里有三种方法来检查两个字符串是否是变位词。我还包括了一个JUnit测试来验证各种包含变位词和非变位词的字符串。

import java.util.Arrays;

/**
 * Java program - String Anagram Example.
 * This program checks if two Strings are anagrams or not
 *
 * @author Javin Paul
 */
public class AnagramCheck {
   
    /*
     * One way to find if two Strings are anagram in Java. This method
     * assumes both arguments are not null and in lowercase.
     *
     * @return true, if both String are anagram
     */
    public static boolean isAnagram(String word, String anagram){       
        if(word.length() != anagram.length()){
            return false;
        }
       
        char[] chars = word.toCharArray();
       
        for(char c : chars){
            int index = anagram.indexOf(c);
            if(index != -1){
                anagram = anagram.substring(0,index) + anagram.substring(index +1, anagram.length());
            }else{
                return false;
            }           
        }
       
        return anagram.isEmpty();
    }
   
    /*
     * Another way to check if two Strings are anagram or not in Java
     * This method assumes that both word and anagram are not null and lowercase
     * @return true, if both Strings are anagram.
     */
    public static boolean iAnagram(String word, String anagram){
        char[] charFromWord = word.toCharArray();
        char[] charFromAnagram = anagram.toCharArray();       
        Arrays.sort(charFromWord);
        Arrays.sort(charFromAnagram);
       
        return Arrays.equals(charFromWord, charFromAnagram);
    }
   
   
    public static boolean checkAnagram(String first, String second){
        char[] characters = first.toCharArray();
        StringBuilder sbSecond = new StringBuilder(second);
       
        for(char ch : characters){
            int index = sbSecond.indexOf("" + ch);
            if(index != -1){
                sbSecond.deleteCharAt(index);
            }else{
                return false;
            }
        }
       
        return sbSecond.length()==0 ? true : false;
    }
}

字符串变位词exmaple的JUnit测试用例

这是我们对anagramcheck类的三个方法的JUnit测试,我们实际上用类似的输入集测试了所有方法。

import org.junit.Test;
import static org.junit.Assert.*;

/**
 * JUnit test class to test various anagram program for various String input.
 */
public class StringAnagramTest {
   
 
    @Test
    public void testIsAnagram() {
        assertTrue(AnagramCheck.isAnagram("word", "wrdo"));
        assertTrue(AnagramCheck.isAnagram("mary", "army"));
        assertTrue(AnagramCheck.isAnagram("stop", "tops"));
        assertTrue(AnagramCheck.isAnagram("boat", "btoa"));
        assertFalse(AnagramCheck.isAnagram("pure", "in"));
        assertFalse(AnagramCheck.isAnagram("fill", "fil"));
        assertFalse(AnagramCheck.isAnagram("b", "bbb"));
        assertFalse(AnagramCheck.isAnagram("ccc", "ccccccc"));
        assertTrue(AnagramCheck.isAnagram("a", "a"));
        assertFalse(AnagramCheck.isAnagram("sleep", "slep"));
       
    }
   
    @Test
    public void testIAnagram() {
        assertTrue(AnagramCheck.iAnagram("word", "wrdo"));
        assertTrue(AnagramCheck.iAnagram("boat", "btoa"));
        assertFalse(AnagramCheck.iAnagram("pure", "in"));
        assertFalse(AnagramCheck.iAnagram("fill", "fil"));
        assertTrue(AnagramCheck.iAnagram("a", "a"));
        assertFalse(AnagramCheck.iAnagram("b", "bbb"));
        assertFalse(AnagramCheck.iAnagram("ccc", "ccccccc"));
        assertFalse(AnagramCheck.iAnagram("sleep", "slep"));
       
    }
    
    @Test
    public void testcheckAnagram() {
        assertTrue(AnagramCheck.checkAnagram("word", "wrdo"));       
        assertFalse(AnagramCheck.checkAnagram("b", "bbb"));
        assertFalse(AnagramCheck.checkAnagram("ccc", "ccccccc"));
        assertTrue(AnagramCheck.checkAnagram("a", "a"));
        assertFalse(AnagramCheck.checkAnagram("sleep", "slep"));
        assertTrue(AnagramCheck.checkAnagram("boat", "btoa"));
        assertFalse(AnagramCheck.checkAnagram("pure", "in"));
        assertFalse(AnagramCheck.checkAnagram("fill", "fil"));
       
    }
}

Output
Testsuite: StringAnagramTest
Tests run: 3, Failures: 0, Errors: 0, Time elapsed: 0.094 sec

我们的anagramcheck类包含3个静态方法来验证字符串是否为变位词。首先,获取第一个字符串的字符数组并循环遍历它,然后在第二个字符串中查找该字符,并使用substring方法删除它。如果第二个字符串不包含字符,则立即返回false。测试结束时,如果第二个字符串为空,则两个字符串都是变位词,因为它们包含相同的字符集。为了提高性能,我们在这个方法的最开始就检查了长度,因为两个长度不同的字符串不能互相变位。第三个方法与第一个方法完全相同,只是它使用StringBuilder的DeleteCharat(int index)方法删除字符。