比较两个数组，然后返回第一个显示的索引

Question

我有一个任务，我在考虑这一点，但我没有提出正确的答案。

在您选择的语言中，写一个函数，该功能获取一个名为str的字符串和名为SET的字符串。

该函数将返回STR。

中的任何字符的首次出现的索引。

例如：str =＆quot; hellohellohellohelloistom！＆quot;set =＆quot; t98765！＆quot'

该函数将返回22（str中的'5'索引）。确保时间复杂性不大于两个字符串的长度-O（m n）假设字符串仅包含ASCII字符。

我正在考虑这件事，我想到了与分裂和征服这样做。我的基本案例始终是o（1），而我在较小的问题中划分了问题，直到得到答案。问题在于，使用该解决方案，复杂性将为O（log n）。

我认为另一个批准是制作一套。但是我仍然真的不知道如何解决这个问题。有任何想法??

Answer 1

此程序用swift

编写

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"))

或其他耗时较少的解决方案

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")) 

注意：

1. 如果找不到任何字符，则它将返回nil
2. 这是情况敏感比较

希望这能解决您的问题。

Answer 2

由于所有涉及的字符串仅包含ASCII字符，然后使用constant memory，可以在O(LengthOf(str) + LengthOf(set))中求解。

这是" C"语言中的代码：

//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] != '')    
    {
        hash[set[i]] = i;
        ++i;
    }
    i = 0;
    while(str[i] != '')
    {
        if(hash[str[i]] != -1)
        {
            *index_of_set = hash[str[i]];
            return i;
        }
        ++i;
    }
    *index_of_set = -1;
    return -1;
}

逻辑通过记录hash表中所有set字符的位置/索引（> = 0），然后解析str的位置/索引（> = 0），并检查str的当前字符是否存在于hash表中。

。

index_of_set还将报告set中CC_9中字符的索引。如果index_of_set = -1，则找不到任何出现。

Answer 3

感谢您的帮助！

这也是c＃。

中的代码

欢呼，

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] != '' && i < set.Length - 1);
        i = 0;
        while (str[i] != '')
        {
            if (hash[str[i]] != -1)
            {
                return i;
            }
            ++i;
        }
        return -1;
    }