Une question d'entrevue - Split texte en sous-chaînes selon les règles

idée

Une approche gourmande est la voie à suivre: p>

• Si le texte actuel est vide, vous avez terminé. LI>
• Prenez les premiers n personnages. Si l'un d'entre eux est un chiffre, il s'agit d'une nouvelle sous-chaîne. Coupez-le et allez à commencer. Li>
• Sinon, étendez le segment sans chiffres à la plupart des caractères M. Ceci est une nouvelle sous-chaîne. Coupez-le et allez à commencer. Li> ul>

  Preuve H2>

  Voici une preuve de réductio-ad-absurdum que ce qui précède génère une solution optimale. Supposons qu'il y a une meilleure scission que la scission gourmande. Passons au point où les deux divisions commencent à differser et à supprimer tout avant ce point. P>

  cas 1) un chiffre parmi les premiers caractères. Strong> P>

  Supposons qu'il y a une entrée pour laquelle la coupant les premiers caractères ne peut pas donner une solution optimale. P> xxx pré>

  Cependant, le deuxième segment de la solution de mieux placée peut être toujours raccourci du côté gauche, et le premier étendu à n caractères, sans modifier le nombre de segments. Par conséquent, une contradiction: cette scission n'est pas meilleure que la scission gourmande. P>

  Cas 2) Pas de chiffre parmi les premiers caractères K (N p>

  suppose qu'il y a une entrée pour laquelle couper les premiers caractères K ne peut pas donner une solution optimale. p> xxx pré>

  à nouveau, la division "meilleure" peut être transformé, sans modifier le nombre de segments, à la scission gourmande, qui contredit l'hypothèse initiale selon laquelle il y a une scission meilleure que la scission gourmande. P>

  Par conséquent, la scission gourmande est optimale. Q.e.d. P>

  Mise en œuvre (Python) H2>

  public class SO {
     public List<String> go(int m, int n, String text) {
        if (text == null)
           return Collections.emptyList();
        List<String> chunks = new ArrayList<String>();
  
        int i = 0;
        int j = 0;
        while (j < text.length()) {
           i = j;         
           j = Math.min(text.length(), j + n);
           boolean ok = true;
           for (int k = i; k < j; k++) 
              if (Character.isDigit(text.charAt(k))) {
                 ok = false;              
                 break;                   
              }                   
           if (ok)        
              while (j < text.length() && j - i < m && !Character.isDigit(text.charAt(j)))
                 j++;                     
           chunks.add(text.substring(i, j));
        }         
        return chunks;
     }    
  
     @Test
     public void testIt() {
        Assert.assertEquals(
           Arrays.asList("asdas", "d332", "4asd", "fsdxf", "23"),
           go(5, 4, "asdasd3324asdfsdxf23"));
     }    
  }
  

bolo a fourni un algorithme gourmand dans sa réponse et a demandé un contre-exemple. Eh bien, il n'y a pas de contre-exemple parce que c'est une approche parfaitement correcte. Voici la preuve. Bien que ce soit un peu verbeux, il arrive souvent que la preuve soit plus longue que l'algorithme lui-même :)

Imaginons que nous avons une entrée de longueur l et construit une réponse A avec notre algorithme. Maintenant, supposons qu'il y ait une meilleure réponse B . I.e., B a moins de segments que A .

disons, premier segment dans A a la longueur la et dans b - lb . la > = lb car nous avons choisi le premier segment dans A pour avoir une longueur maximale possible. Et si lb < la , nous pouvons augmenter la longueur du premier segment dans B sans augmenter le nombre total de segments dans B . Cela nous donnerait une autre solution optimale B ', ayant le même premier segment que a .

maintenant, supprimez ce premier segment de A et B ' et répétez le fonctionnement de la longueur l' < l . Faites-le jusqu'à ce qu'il ne reste plus de segments. Cela signifie que la réponse A est égale à une solution optimale.