AC straight forward solution and two DP solutions, MLE and TLE respectively


  • 0

    I am new to DP and picked this problem to practice my DP skill, after I try my best to solve this problem with DP (I don't know if it is real DP) , I found that both of my solutions were not accepted, MLE and TLE respectively, here are my codes:

    	/*
    	 * Memory Limit Exceeded
    	 */
    	public boolean isSubsequence(String s, String t) {
    		if (s.length() == 0)
    			return true;
    		if (s.length() == t.length())
    			return s.equals(t);
    		if (s.length() > t.length())
    			return false;
    
    		boolean[][] result = new boolean[s.length()][t.length()];		// too many memory here
    		result[0][0] = s.charAt(0) == t.charAt(0);
    		for (int i = 1; i < t.length(); i++)
    			result[0][i] = result[0][i - 1] || s.charAt(0) == t.charAt(i);
    
    		for (int i = 1; i < s.length(); i++) {
    			for (int j = i + 1; j < t.length(); j++) {
    				result[i][j] = result[i][j - 1] || (result[i - 1][j - 1] && s.charAt(i) == t.charAt(j));
    			}
    		}
    		return result[s.length() - 1][t.length() - 1];
    	}
    
    	/*
    	 * Time Limit Exceeded
    	 */
    	public boolean isSubsequenceV2(String s, String t) {
    		if (s.length() == 0)
    			return true;
    		return isSubsequenceHelper(s, s.length() - 1, t, t.length() - 1);
    	}
    
    	private boolean isSubsequenceHelper(String s, int index1, String t, int index2) {
    		if (index1 == 0)
    			return t.substring(0, index2 + 1).contains(s.substring(0, index1 + 1));
    		if (index1 > index2)
    			return false;
    		return isSubsequenceHelper(s, index1, t, index2 - 1)
    				|| (isSubsequenceHelper(s, index1 - 1, t, index2 - 1) && s.charAt(index1) == t.charAt(index2));		// too many recursion here
    	}
    	
    	// linear solution
    	public boolean isSubsequenceV3(String s, String t) {
    		int indexOfS = 0;
    		int indexOfT = 0;
    		while (indexOfS < s.length() && indexOfT < t.length()) {
    			if (s.charAt(indexOfS) == t.charAt(indexOfT))
    				indexOfS++;
    			indexOfT++;
    		}
    		return indexOfS == s.length() && indexOfT < t.length();
    	}
    

    Anyone can point out that if I am use the real DP idea? Thanks in advance!!


Log in to reply
 

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