Plus rapide façon de vérifier si nous pouvons écrire un message à partir de lettres données

Question

Je devais écrire une fonction qui prend en entrée deux chaînes. L'un est le message que je veux écrire et le second est donné des lettres. Les lettres sont classées de manière aléatoire. Il n'est pas garanti que chaque lettre se répète autant de fois. Certaines lettres peuvent être complètement manquantes. La fonction doit déterminer si je peux écrire un message avec les lettres données et il doit renvoyer vrai ou faux en conséquence.

Je l'ai codé et je pense que c'est très rapide, mais comment puis-je l'améliorer en gardant à l'esprit que la chaîne avec des lettres serait très grande alors que le message serait très court?

Y a-t-il un moyen le plus rapide?

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

} 

Pour la grande taille du bol et de plus petite taille msg je trouve que ce serait mor efficace:

public (message String, String bowlWithLetters) statique canConstructMessageSorted booléen { 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; 
} 

Answer 1

Vous opérez sur O (message.size + letters.size). C'est la plus basse complexité temporelle que je puisse comprendre. En vous référant au le plus rapide, vous pouvez toujours faire plus. Par exemple, définir la méthode

public static char[] stringToCharacterList(String message) 

et de ne l'utiliser qu'une seule fois est techniquement inefficace. Vous auriez pu simplement placer ce corps de code dans la méthode canConstructMessage(), en sauvant qu'un autre élément ne soit placé et retiré de la pile. Bien que ce soit un petit fragment de temps, quand vous dites le plus rapide, il pourrait être intéressant de parler.

Answer 2

Pour chaque lettre de letters, supprimez-en une copie du message. Si le message se termine vide, la réponse est « oui »:

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

Si la réutilisation des lettres est permis, vous pouvez le faire en 1 ligne:

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

Answer 3

J'ai trouvé ce serait plus efficace pour taille de grand bol et petit taille de 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; 
}