Perfect.Hash
BAN USERHum. It works for both cases, in 1st case it returned 2, and in the 2nd case -1.
- Perfect.Hash January 27, 2013O(n) solution:
// first - distance, second - petrol
typedef std::pair<int, int> Station;
typedef vector<Station> PetrolStations;
int GetStartStationIdx(PetrolStations stations)
{
int result = stations.size() - 1;
int petrol = 0;
for(int idx = stations.size() - 2;idx>=0;--idx)
{
if ( petrol>0 )
petrol = 0;
const Station& station = stations[idx];
petrol += (station.second - station.first);
if ( petrol>=0 )
result = idx;
}
petrol = 0;
for(int i = 0;i<stations.size();++i)
{
PetrolStations::size_type idx = (result + i)%stations.size();
const Station& station = stations[idx];
petrol += (station.second - station.first);
if ( petrol<0 )
{
result = -1;
break;
}
}
return result;
}
I think following algorithm should be applied:
When we find several ? symbols in the middle of the string, we should calculate
a) How much symbols should be appended to the left of ???? to complement p string.
b) How much symbols should be appended to the right of ???? to complement p string.
if a<b - append symbols to the left.
For example:
S: TERR????RRA
p: TERRA
step #1: TERRA???RRA
step #2: TERRA?TERRA
Repeat algorithm till we have any ? symbol in the S string.
Processing from the end of a string is not always a solution, consider following example:
S: AKTAK??????
p: AKTAK
if we start for the end of the string, than result will contain only 2 substrings: AKTAKAAKTAK
but if we'll move forward, we'll have 3 substrings: AKTAKTAKTAK
Aha, you're right. Looks like I misunderstood the question. The solution should be OK now )
- Perfect.Hash January 27, 2013