更快的方法來檢查，如果我們可以從給定的字母

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; 
    }; 

} 

對於大碗尺寸和更小的尺寸味精我發現，這將是有效的MOR：

公共靜態布爾canConstructMessageSorted（字符串消息，字符串bowlWithLetters）{ INT計數器= 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（message.size + letters.size）。這是我手頭可以計算出的最低時間複雜度。參考最快的方式，總是有更多的事情可以做。例如，定義方法

public static char[] stringToCharacterList(String message) 

並且只使用一次在技術上是時間效率低下的。您可以簡單地將該代碼體放入canConstructMessage（）方法中，從而保存另一個項目並將其從堆棧中取出。雖然這只是一小段時間，但當你說最快的時，可能值得一提。

Answer 2

對於letters每一個字母，從所述消息中移除的其1個拷貝。如果消息最終空，答案是「是」：

public static boolean canConstructMessage(String message, String letters) { 
    return letters.chars().boxed().collect(Collectors.toSet()) 
     .containsAll(message.chars().boxed().collect(Collectors.toSet()); 
} 

Answer 3

我發現這將是更有效的：

public static boolean canConstructMessage(String message, String letters) { 
    for (int i = 0; i < letters.length(); i++) 
     message = message.replaceFirst("" + letters.charAt(i), ""); 
    return message.isEmpty(); 
}  

如果重新使用字母是允許的，你可以在1號線做大碗大小小味精大小：

public static boolean canConstructMessageSorted(String message, String bowlWithLetters) { 
    int counter = 0; 
    boolean 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; 
}