This simple BFS solution is giving TLE. I guess there might be some infinite loop, but don't know why.

general
,
1

here is the problem

#include <string.h>
#include <vector>
#include <queue>
#include <stdio.h>

using namespace std;

class Node
{
	public:
	int idx, steps;
};

int main()
{
	char str[100001];
	scanf("%s", str);
	int len = strlen(str);
	
	vector<int> adj[10];
	for(int i = 0; i < len; i++)
		adj[str[i] - '0'].push_back(i);
	
	int idx, chi, size, steps;
	Node tmpn;
	tmpn.idx = 0;
	tmpn.steps = 0;
	queue<Node> que;
	que.push(tmpn);
	bool * visited = new bool[len];
	for(int i = 0; i < len; i++)
		visited[i] = false;
		
	while(!que.empty())
	{
		tmpn = que.front();
		que.pop();
		idx = tmpn.idx;
		steps = tmpn.steps;
		chi = str[idx] - '0';
		
		if(visited[idx])
			continue;
		visited[idx] = true;
			
		if(idx == (len - 1))
		{
			printf("%d\n", tmpn.steps);
			return 0;
		}
		
		if(visited[idx + 1] == false)
		{
			tmpn.idx = idx + 1;
			tmpn.steps = steps + 1;
			que.push(tmpn);
		}
		
		if(idx > 0 && visited[idx - 1] == false)
		{
			tmpn.idx = idx - 1;
			tmpn.steps = steps + 1;
			que.push(tmpn);
		}
			
		size = adj[chi].size();
		for(int j = 0; j < size; j++)
		{
			if(visited[adj[chi][j]] == false)
			{
				tmpn.idx = adj[chi][j];
				tmpn.steps = steps + 1;
				que.push(tmpn);
			}
		}
	}
	return 0;
}
2

Your solution wont finish in acceptable time for the problem. Remember that BFS ist O(E). In a string with O(n) digits of some kind there are O(n^2) edges between those digits. For N=10^5 O(N^2) is too much.

1 Like
3

Thanks. I kept thinking that maybe my code is entering an infinite loop for some test case :slight_smile: