Memory Limit Exceeded


  • 1
    A

    I'm trying to use dijkstra's algorithm to solve this. It works fine in my local machine, but fails with Memory Limit Exceeded here. My best bet is that it's because I make a copy of the nodes in unordered_set. I'm fairly new to C++, and am doing that only because I couldn't find a way to access the values in unordered_set with a position index. Any workaround for that?

    struct Het
    {
    	int i;
    	int l;
    	vector<int> prev;
    
    	Het(int it, int lt) : i(it), l(lt) {}
    };
    
    struct He
    {
    	 Het *het;
    	 int i;
    
    	 He(Het *hett, int it) : het(hett), i(it) {}
    };
    
    
    class Heap
    {
    	vector<He*> h;
    	int ei;
    public:	
    
    	Heap()
    	{
    		ei=-1;
    	}
    
    	He* Insert(Het *het)
    	{
    		ei++;
    		He *he = new He(het, ei);		
    		h.push_back(he);
    		HeapifyUp(he);
    		return he;
    	}
    
    	void swap(He* he1, He* he2)
    	{
    		h[he1->i] = he2;
    		h[he2->i] = he1;
    
    		int t = he1->i;
    		he1->i = he2->i;
    		he2->i = t;
    	}
    
    	He* PopSmallest()
    	{
    		He* toReturn = h[0];
    		swap(h[0], h[ei]);
    		ei--;
    
    		int n=0, l, r, s;
    
    		while(true)
    		{
    			s=n; l=n*2+1; r=l+1;
    			if(l<=ei && h[l]->het->l < h[s]->het->l)
    			{
    				s=l;
    			}
    
    			if(r<=ei && h[r]->het->l < h[s]->het->l)
    			{
    				s=r;
    			}
    
    			if(s==n)
    			{
    				break;
    			}
    			else
    			{
    				swap(h[n],h[s]);
    				n=s;
    			}
    		}
    
    		return toReturn;
    	}
    
    	void HeapifyUp(He *he)
    	{
    		assert(he->i <= ei);
    
    		int n=he->i,l, p;
    
    		while(true)
    		{
    			l=n;
    			p= n>0 ? (n-1)/2 : -1;
    
    			if(p>=0 && h[p]->het->l > h[l]->het->l)
    			{
    				l=p;
    			}
    
    			if(l==n)
    			{
    				break;
    			}
    			else
    			{
    				swap(h[l],h[n]);
    			}
    			n=l;
    		}
    	}
    
    };
    
    class Solution {
    public:
    	vector<vector<string>> res;
    	vector<vector<const string*>> tRes;
    	vector<const string *> s;
    	Heap h;
    	vector<He*> hes;
    	int ex;
    	
    	void RA(vector<const string*> &soFar, int i)
    	{
    		soFar.push_back(s[i]);
    
    		if(i==0)
    		{
    			tRes.push_back(soFar);
    		}
    		else
    		{
    			auto prev = hes[i]->het->prev;
    			for(int j=0; j<prev.size(); j++)
    			{
    				RA(soFar, prev[j]);
    			}
    		}
    		soFar.pop_back();
    	}
    
    	int GetL(const string & s1, const string & s2)
    	{
    		bool diffFound = false;
    
    		for(unsigned int i=0; i<s1.length(); i++)
    		{
    			if(s1[i]!=s2[i])
    			{
    				if(diffFound)
    				{
    					return INT_MAX;
    				}
    				else
    				{
    					diffFound = true;
    				}
    			}
    		}
    
    		return 1;
    	}
        vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) 
    	{
    		dict.erase(start);
    		dict.erase(end);
    
    		s.push_back(&start);
    
    		for (auto it = dict.begin(); it != dict.end(); ++it )
    		{
    			//string *st = new string(*it);
    			const string &st = *it;
    			s.push_back(&st);
    		}
    
    		s.push_back(&end);
    
    		int c = s.size();
    
    		int* m = new int[c*c];
    
    		for(int i=0; i<c; i++)
    		{
    			m[i*c+i]=0;
    			for(int j=i+1; j<c; j++)
    			{
    				m[i*c+j] = GetL(*s[i], *s[j]);
    				m[j*c+i] = m[i*c+j];
    			}
    		}
    
    		for(int i=0; i<c; i++)
    		{
    			m[i*c] = 0;
    			m[(c-1)*c+i]=0;
    		}
    
    		for(int i=0; i<c; i++)
    		{
    			hes.push_back(h.Insert(new Het(i, m[i])));
    		}
    
    		while(true)
    		{
    			Het &cn = *(h.PopSmallest()->het);
    			if(cn.i == c-1)
    			{
    				break;
    			}
    
    			for(int j=0; j<c; j++)
    			{
    
    				if(j==cn.i || cn.l==INT_MAX || m[cn.i*c+j] == INT_MAX)
    				{
    					continue;
    				}
    
    				Het &nn = *(hes[j]->het);
    
    				int nl = cn.l + m[cn.i*c+j];
    
    				if(nl <= nn.l)
    				{
    					if(nl < nn.l)
    					{
    						nn.l = nl;
    						nn.prev.clear();
    						h.HeapifyUp(hes[j]);
    					}
    					nn.prev.push_back(cn.i);					
    				}
    			}
    		}
    
    		vector<const string*> tmp;
    
    		RA(tmp, c-1);
    
    		for(int i=0; i<tRes.size(); i++)
    		{
    			vector<string> t;
    			for(int j=tRes[i].size()-1; j>=0; j--)
    			{
    				t.push_back(*tRes[i][j]);
    			}
    			res.push_back(t);
    			t.clear();
    		}
    
    		return res;
        }
    } sol;

  • 2
    S

    Creating a graph based on given dictionary is not efficient way, it waste of time and memory. Since the dictionary might be large, but for one particular test case, it may only touch a few words in it.

    Here is a answer to question of Word Ladder, which get TLE due to create a graph of dictionary. I hope you can get hint from it.


  • 0
    A
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.