Paraula en un arbre V40142
Direm que un BinTree<char> T representa una paraula word, formada pels caràcters c1c2… cn, amb n≥ 0, si hi ha un camí a l’arbre començant des de l’arrel i de longitud n tal que els valors dels nodes del camí formen word. Implementeu eficientment la funció count_word_in_paths, especificada a continuació:
/** * @pre `word` té almenys una lletra * @post es retorna el nombre de camins que representen * la paraula word des de l'arrel */ int count_word_in_paths(const vector<char>& word, const BinTree<char>& T);
Per exemple, per a la paraula "dia" si l’arbre és t1, el resultat és 0, si l’arbre és t2 el resultat és 3 i si l’arbre és t3 el resultat és 1.
t1 = d t2 = d t3 = d
/ \ / \ / \
d d i i i i
/ \ / / \ / \
w i a a a a b
/ \ /
k a r
Observació
Només cal que envieu el codi de la funció en un fitxer .cc, a la icona del gatet teniu un .tar per poder compilar i provar la vostra solució.
Sample session
count_word_in_paths("a", "a(b,)") → 1 count_word_in_paths("ab", "a(b,)") → 1 count_word_in_paths("abc", "a(b,)") → 0 count_word_in_paths("abc", "a(b(c,x),b(y,c))") → 2 count_word_in_paths("abc", "a(b,c(d,))") → 0
Information
- Author
- PRO2
- Language
- Catalan
- Other languages
- Spanish
- Official solutions
- C++
- User solutions
- C++