Google Problem — any help?

Правка en1, от imaking, 2019-10-20 22:04:09

We have a two strings: A and B. We need to find miniumum number of times that we could concatenate B to get A. Also we can omit any number of letters from B in any of the concatenations if we want. Example:

A = "ZAZA"
B = "BAZ"

A is obtained from 3 copies of B A= (--Z)(-AZ)(-A-)

Can you suggest any algorithmic approach which is better than O(nm) where n is length of A and m is length of B.

Теги #interview, #strings

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский imaking 2020-11-22 23:57:57 7
en1 Английский imaking 2019-10-20 22:04:09 460 Initial revision (published)