更快的方法来检查我们是否可以从给定的信件中写消息

Question

我需要编写一个以两个字符串作为输入的函数。一个是我要写的信息，第二个是给我的信。字母的顺序是随机的。不能保证每个字母出现的次数是相似的。有些字母可能会完全丢失。函数应该确定我是否可以用给定的字母写消息，并且它应该相应地返回true或false。

我编码了它，我认为它是非常快的，但我如何改进它，记住，带字母的字符串将是非常大的，而消息将是非常短的？

有最快的方法吗？

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class LetterBowl {

    public static void main(String []args){
        String message = generateRandomStringUpToThousandChars();
        String bowlWithLetters = generateRandomStringUpToThousandChars();

        if(canConstructMessage(message, bowlWithLetters)) {
            System.out.println("Message '" + message + "' can be constructed with letters from bowl : " + bowlWithLetters);
        }
     }


    public static boolean canConstructMessage(String message, String letters) {
        Map<Character,Integer> letterMap = stringToCharacterMap(letters);
        char[] messageList = stringToCharacterList(message);

        for(char c : messageList) {
            if (!containsLetterAndSubtract(c,letterMap))
                return false;
        }
        return true;
    }


    // checks if map(bowl) contains char andsubtract one char from map(or removes it if it is last one)
    public static boolean containsLetterAndSubtract(char c, Map<Character,Integer> letterMap) {
        if(letterMap.containsKey(c)) {
            if(letterMap.get(c) > 1) {
                letterMap.put(c, letterMap.get(c) - 1);
            } else {
                letterMap.remove(c);
            }
            return true;
        }
        return false;
    }

    public static char[] stringToCharacterList(String message) {
        return message.replaceAll(" ", "").toCharArray();
    }

    public static Map<Character,Integer> stringToCharacterMap(String s) {
        Map<Character,Integer> map = new HashMap<Character,Integer>();

        for (char c : s.toCharArray()) {
            if(map.containsKey(c))
                map.put(c, map.get(c) + 1);
            else
                map.put(c, 1);
        }
        return map;
    }

    public static String generateRandomStringUpToThousandChars(){
        char[] chars = "abcdefghijklmnopqrstuvwxyz".toCharArray();

        StringBuilder sb = new StringBuilder();
        Random random = new Random();
        for (int i = 0; i < random.nextInt(1000); i++) {
            char c = chars[random.nextInt(chars.length)];
            sb.append(c);
        }
        String output = sb.toString();

        return output;
    }; 

}

对于大碗大小和较小的味精大小，我发现这将是非常有效的：

公共静态布尔canConstructMessageSorted（String message,String bowlWithLetters）{int counter=0；布尔HasLetter；

    //sorting
    char[] chars = bowlWithLetters.toCharArray();
    Arrays.sort(chars);
    String sortedBowl = new String(chars);

    //sorting
    chars = message.toCharArray();
    Arrays.sort(chars);
    String sortedMsg = new String(chars);

    for (int i = 0; i < sortedMsg.length(); i++) {
        hasLetter = false;
        for(  ; counter < sortedBowl.length() ; counter++) {
            if(sortedMsg.charAt(i) == sortedBowl.charAt(counter)) {
                hasLetter = true;
                break;
            }
        }
        if(!hasLetter) return false;
    }
    return true;
}

Answer 1

您的操作为O（消息大小+字母大小）。这是我手头能算出的最低最坏情况下的时间复杂度。提到最快的方法，总有更多的你可以做。例如,定义方法

public static char[] stringToCharacterList(String message)

而且只使用一次在技术上是没有时间效率的。您可以简单地将代码主体放在canConstructMessage（）方法中，从而避免将另一个项放在堆栈上，并从堆栈中取出。虽然这是一小段时间，但当你说最快的时候，它可能是值得谈论的。