Vergleichen Sie zwei Arrays und geben Sie den Index der ersten Erscheinung

Question

Ich habe eine Aufgabe zu tun, und ich habe darüber nachgedacht, aber ich komme nicht mit der richtigen Antwort.

Schreiben Sie in einer Sprache Ihrer Wahl eine Funktion, die eine Zeichenfolge mit dem Namen str und eine Zeichenfolge mit dem Namen set erhält.

Die Funktion gibt den Index des ersten Auftretens eines beliebigen Zeichens aus set in str zurück.

Zum Beispiel: str = "hallohellohellohelloistom!" set = "t98765!"

Die Funktion gibt 22 (Index von '5' in str) zurück. Stellen Sie sicher, dass die Zeitkomplexität nicht größer ist als die Länge der beiden Zeichenfolgen. O (m + n) Angenommen, die Zeichenfolge enthält nur ASCII-Zeichen.

Ich habe darüber nachgedacht und ich dachte darüber nach, es mit Teile und Herr zu machen. Ich habe einen Basisfall, der immer O (1) ist und das Ich teile das Problem in kleinere Probleme, bis ich die Antwort bekomme. Das Problem ist, dass bei dieser Lösung die Komplexität O (log n) ist.

Der andere Ansatz, den ich dachte, war, ein Set zu machen. Aber ich weiß immer noch nicht wirklich, wie ich dieses Problem angehen soll. Irgendwelche Ideen??

Answer 1

Da alle beteiligten Zeichenfolgen nur ASCII-Zeichen enthalten, kann diese unter Verwendung von constant memory in O(LengthOf(str) + LengthOf(set)) gelöst werden.

Hier ist der Code in "C" Sprache:

//ReturnValues: 
//-1 : if no occurrence of any character of set is found in str 
//value >=0 : index of character in str. 
int FindFirstOccurenceOfAnyCharacterInSet(const char *str, const char *set, int *index_of_set) 
{ 
    char hash[256]; 
    int i = 0; 
    while(i < 256) 
    { 
     hash[i] = -1; 
     ++i; 
    } 
    i = 0; 
    while(set[i] != '\0')  
    { 
     hash[set[i]] = i; 
     ++i; 
    } 
    i = 0; 
    while(str[i] != '\0') 
    { 
     if(hash[str[i]] != -1) 
     { 
      *index_of_set = hash[str[i]]; 
      return i; 
     } 
     ++i; 
    } 
    *index_of_set = -1; 
    return -1; 
} 

Logic arbeitet, indem sie die Position/Indizes der Aufnahme (die> = 0) alle Zeichen von set in hash Tabelle und dann str Parsen und Überprüfen, ob das aktuelle Zeichen str in hash Tabelle vorhanden ist.

index_of_set wird auch den Index des Zeichens in set, die in str gefunden wird. Wenn index_of_set = -1 dann wurde kein Vorkommen gefunden.

Answer 2

Dieses Programm in Swift

geschrieben

let str = "hellohellohellohelloistom!" 
let set = "t98765!" 

func findFirstAppearance(str : String , set : String) -> Int? { 
    var index : Int? 

mainLoop: for setCharacter in set.characters{ 

    for (indexOfChar,strCharacter) in str.characters.enumerate(){ 

     if strCharacter == setCharacter{ 
     index = indexOfChar 
      break mainLoop 
     } 
    } 

} 

return index 
} 

print(findFirstAppearance(str, set: set)) 
print(findFirstAppearance("helloWorld", set: "546Wo")) 

oder eine andere Lösung mit weniger zeitraubend

let str = "hellohellohellohelloistom!" 
let set = "t98765!" 

func findFirstAppearance(str : String , set : String) -> Int? { 
    var index : Int? 

    mainLoop: for setCharacter in set.characters{ 

     if let range = str.rangeOfString(String(setCharacter)){ 

      index = str.startIndex.distanceTo(range.startIndex) 

      break 
     } 

    } 

    return index 
} 

print(findFirstAppearance(str, set: set)) 
print(findFirstAppearance("helloWorld", set: "546Wo")) 

Hinweis:

1. wenn irgendein Zeichen, das nicht gefunden wird, dann wird es Fehlanzeige
2. ist es Groß-und Kleinschreibung Vergleich

Hoffe, dass dies Ihr Problem lösen wird.

Answer 3

Danke für die Hilfe !!

Hier ist auch der Code in C#.

Cheers,

public static int FindFirstOccurenceOfAnyCharacterInSet(string str, string set) 
    { 
     var hash = new int[256]; 
     int i = 0; 
     while (i < 256) 
     { 
      hash[i] = -1; 
      ++i; 
     } 
     i = 0; 
     do 
     { 
      hash[set[i]] = i; 
      ++i; 
     } while (set[i] != '\0' && i < set.Length - 1); 
     i = 0; 
     while (str[i] != '\0') 
     { 
      if (hash[str[i]] != -1) 
      { 
       return i; 
      } 
      ++i; 
     } 
     return -1; 
    }