Как вернуть самые длинные слова из массива?

given 2 arrays wrds[] , chars[] as an input to a function such that
wrds[] = [ "abc" , "baa" , "caan" , "an" , "banc" ]
chars[] = [ "a" , "a" , "n" , "c" , "b"]

Функция должна возвращать самое длинное слово из слов [], которое может быть построено из символов в массиве chars []. для примера выше - "caan", "banc" должен быть возвращен

Примечание: Когда используется символ в массиве chars [], его нельзя использовать снова. eg: words[] = [ "aat" ] characters[] = [ "a", "t" ] тогда слово "aat" не может быть построено, так как мы имеем только 1 "a" в символах [].

Есть виды андеров онлайн, но они не написаны в Objective C.Can, кто-нибудь поможет мне решить этот вопрос в OC?

2 ответа

Сначала пройдите через массив слов, по одному слову за раз, выкинув все слова, которые не могут быть сформированы из второго массива. Чтобы сделать это, для каждого слова, пройдите через символы слова, выкинув этот символ из второго массива. Если мы перейдем к символу, который не во втором массиве, это слово не может быть сформировано из этих символов.

Теперь у нас есть массив, состоящий исключительно из слов, которые могут быть сформированы из этих символов. Теперь отсортируйте этот массив по длине слова, самый длинный сперва. Теперь начните ходить по массиву, глядя на длину каждого слова. Когда значение этой длины изменяется, остановитесь; вы нашли все самые длинные слова.


// Program do to do the same in C++
#include <iostream>
#include <string>
#include <map>
#include <vector>
using namespace std;
using std::vector;
vector<char*> match(char** words, int size, char* chars, map<char,int> &second)
{
vector<char*> res;
std::map<char,int> mapi = second;
int currsize = 0;
for(int i = 0; i < size ; i++){ char* wo; wo = words[i]; int s= 0; for( s=0; wo[s] != '\0'; s++){ } if(s < currsize) { //No need to iterate if already found a bigger word //continue to see if the next word if bigger of the same size as currsize continue; } // iterate through the map to see if all the letters present in the first array bool found = true; for(int j = 0; j <s ;="" j++){="" map<char,="" int="">::iterator it = mapi.find(wo[j]); if(it == mapi.end()) { found= false; break; } } if(!found) { continue; } if(s > currsize) { //remove the past res as found a bigger one res.clear(); } //Store this word in the vector as it is one of the biggest word so far res.push_back(wo); currsize = s;
}
return res;
}
int main()
{ map<char, int=""> leters; char* words[5] = {"adc", "baa", "caan", "daanns", "banc"}; char ch1[]= {'a', 'a', 'n', 'c', 'b'}; int chsize = sizeof(ch1); // put the ch1 chars in a map for(int i = 0; i < chsize; i++) { map<char,int>::iterator it =leters.find(ch1[i]); if(it != leters.end()) { it->second = it->second+1; } else { leters.insert(make_pair(ch1[i], 1)); } } char* chars = ch1; vector<char*>v = match(words, 5, ch1, leters); for(vector<char*>::iterator it = v.begin(); it != v.end(); it++) { // it will print the result cout << *it << endl; } return 0;
}
</char*></char*></char,int></char,></s></char,int></char*></char,int></char*></vector></map></string></iostream>

licensed under cc by-sa 3.0 with attribution.