Comment trouver le premier caractère non-répétitif d'une chaîne?

Question

J'ai passé une demi-journée à essayer de comprendre cela et finalement j'ai eu une solution de travail. Cependant, je pense que cela peut être fait de manière plus simple. Je pense que ce code n'est pas vraiment lisible.

Problème: Trouvez le premier caractère non répétitif d'une chaîne.

$ string = "abbcabz"

Dans ce cas, la fonction doit générer "c".

La raison pour laquelle j'utilise concaténation au lieu de $input[index_to_remove] = '' afin de supprimer le caractère d'une chaîne donnée est parce que si je fais ça, il fait juste laisser la cellule vide pour que ma valeur de retour d'entrée de $ [0] ne pas retourne le personnage que je veux retourner.

Par exemple,

$str = "abc"; 
$str[0] = ''; 
echo $str; 

Affichera "bc"

Mais en fait, si je test,

var_dump($str); 

il me donnera:

string(3) "bc" 

ici est mon intention:

Given: input 

while first char exists in substring of input { 
    get index_to_remove 
    input = chars left of index_to_remove . chars right of index_to_remove 

    if dupe of first char is not found from substring 
    remove first char from input 
} 
return first char of input 

code:

function find_first_non_repetitive2($input) { 

    while(strpos(substr($input, 1), $input[0]) !== false) { 

     $index_to_remove = strpos(substr($input,1), $input[0]) + 1; 
     $input = substr($input, 0, $index_to_remove) . substr($input, $index_to_remove + 1); 

     if(strpos(substr($input, 1), $input[0]) == false) { 
      $input = substr($input, 1);  
     } 
    } 
    return $input[0]; 
} 

Answer 1

<?php 
    // In an array mapped character to frequency, 
    // find the first character with frequency 1. 
    echo array_search(1, array_count_values(str_split('abbcabz'))); 

Answer 2

pseudocode:

Array N; 

For each letter in string 
    if letter not exists in array N 
    Add letter to array and set its count to 1 
    else 
    go to its position in array and increment its count 
End for 

for each position in array N 
    if value at potition == 1 
    return the letter at position and exit for loop 
    else 
    //do nothing (for clarity) 
end for 

Fondamentalement, vous trouvez toutes les lettres distinctes dans la chaîne, et pour chaque lettre, vous associer à un compte de combien de de cette lettre existe dans la chaîne. alors vous retournez le premier qui a un compte de 1

La complexité de cette méthode est O (n^2) dans le pire des cas si vous utilisez des tableaux. Vous pouvez utiliser un tableau associatif pour augmenter ses performances.

Answer 3

Cela peut être fait dans le code beaucoup plus lisible à l'aide des fonctions PHP standard:

// Count number of occurrences for every character 
$counts = count_chars($string); 

// Keep only unique ones (yes, we use this ugly pre-PHP-5.3 syntax here, but I can live with that) 
$counts = array_filter($counts, create_function('$n', 'return $n == 1;')); 

// Convert to a list, then to a string containing every unique character 
$chars = array_map('chr', array_keys($counts)); 
$chars = implode($chars); 

// Get a string starting from the any of the characters found 
// This "strpbrk" is probably the most cryptic part of this code 
$substring = strlen($chars) ? strpbrk($string, $chars) : ''; 

// Get the first character from the new string 
$char = strlen($substring) ? $substring[0] : ''; 

// PROFIT! 
echo $char; 

Answer 4

1- utiliser un tri algotithm comme mergesort (ou quicksort a de meilleures performances avec de petites entrées)
2- puis contrôle caractères repetetive

• caractères non repetetive seront simple
  
• repetetvives seront en jachère l'autre
  

Performance: trier + comparer
Performance: O (n log n) + O (n) = O (n log n)
Par exemple

$string = "abbcabz" 

    $string = mergesort ($string) 
    // $string = "aabbbcz" 

ensuite, prenez la première chaîne de forme char puis comparez avec suivante si cela correspond repetetive
passer à la prochaine di caractère fférents et comparer
premier caractère non-appariement est non repetetive

Answer 5

est ici une fonction Scala qui le ferait:

def firstUnique(chars:List[Char]):Option[Char] = chars match { 
    case Nil => None 
    case head::tail => { 
    val filtered = tail filter (_!=head) 
    if (tail.length == filtered.length) Some(head) else firstUnique(filtered) 
    } 
} 

scala> firstUnique ("abbcabz" .ToList)
res5: Option [Char] = Certains (c)

Et voici l'équivalent en Haskell:

firstUnique :: [Char] -> Maybe Char 
firstUnique [] = Nothing 
firstUnique (head:tail) = let filtered = (filter (/= head) tail) in 
      if (tail == filtered) then (Just head) else (firstUnique filtered) 

* principal> firstUnique "abbcabz"

Just 'c'

Vous pouvez résoudre ce plus généralement par abstraire sur des listes de choses qui peut être comparé à l'égalité:

firstUnique :: Eq a => [a] -> Maybe a 

Les chaînes sont juste une telle liste.

Answer 6

$str="abbcade"; 
$checked= array(); // we will store all checked characters in this array, so we do not have to check them again 

for($i=0; $i<strlen($str); $i++) 
{ 
    $c=0; 
    if(in_array($str[$i],$checked)) continue; 

    $checked[]=$str[$i]; 

    for($j=$i+1;$j<=strlen($str);$j++) 
    { 
     if($str[$i]==$str[$j]) 
     { 
      $c=1; 
      break; 
     } 
    } 
    if($c!=1) 
    { 
     echo "First non repetive char is:".$str[$i]; 
     break; 
    } 
} 

Answer 7

Cela devrait remplacer votre code ...

 

$array = str_split($string); 
$array = array_count_values($array); 
$array = array_filter($array, create_function('$key,$val', 'return($val == 1);')); 
$first_non_repeated_letter = key(array_shift($array)); 

Edit: a parlé trop tôt. Supprimé "array_unique", pensé qu'il a effectivement abandonné les valeurs en double. Mais l'ordre des caractères doit être préservé pour pouvoir trouver le premier caractère.

Answer 8

Python:

def first_non_repeating(s): 
for i, c in enumerate(s): 
    if s.find(c, i+1) < 0: 
    return c 
return None 

même en PHP:

function find_first_non_repetitive($s) 
{ 
for($i = 0; i < strlen($s); i++) { 
    if (strpos($s, $s[i], i+1) === FALSE) 
    return $s[i]; 
} 
}