与えられた文字からメッセージを書くことができるかどうかを速く確認する

Question

入力として2つの文字列を取る関数を書く必要がありました。 1つは書きたいメッセージ、2つ目は手紙です。文字はランダムに並べられます。それぞれの文字が同じ回数発生するという保証はありません。 この関数は、指定された 文字のメッセージを書くことができるかどうかを判断する必要があります。それに応じてtrueまたはfalseが返されます。

私はそれをコード化しましたが、それは非常に速いと思いますが、メッセージが非常に短い間に、文字列の文字列が非常に大きくなることをどうすれば改善できますか？

最速の方法はありますか？大きなボウルサイズと小さいMSGサイズの

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）で操作しています。これは、私が把握できる最悪の場合の最も低い時間の複雑さです。 最速の方法を参照すると、いつもより多くのことができます。例えば、方法を定義することは、技術的に時間効率が悪いため、一度しか使用しないでください。そのコードをcanConstructMessage（）メソッド内に置くだけで、別のアイテムを置いてからスタックから取り除くことができます。これは時間のほんの一部ではありますが、といっても最速でと言えば、それについて話す価値があります。

Answer 2

lettersのすべての文字について、メッセージからその1コピーを削除します。メッセージが空を終了した場合、答えは「イエス」です。

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 canConstructMessage(String message, String letters) { 
    return letters.chars().boxed().collect(Collectors.toSet()) 
     .containsAll(message.chars().boxed().collect(Collectors.toSet()); 
} 

Answer 3

私は、これがために、より効率的であるました大きなボウルサイズと小さなmsgサイズ：

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