LintCode: Delete Characters

Delete Characters



Similar Problems:


Description
Input two strings s and t,determine if s can get t after deleting some characters.

1 <= |s|, |t| <= 10^5

String contains only lowercase letters

Example

Given s="abc", t="c" , return True.

Explanation:
s delete 'a' and 'b' to get t.
Given s="a", t="c" , return False.

Explanation:
s cannot get t after deleting some characters.

Github: code.dennyzhang.com

Credits To: lintcode.com

Leave me comments, if you have better ways to solve.


  • Solution: twopointer
// Blog link: https://code.dennyzhang.com/delete-characters
// Basic Ideas: Two pointers
// Complexity: Time O(n+m), Space O(1)
/**
 * @param s: The string s
 * @param t: The string t
 * @return: Return if can get the string t
 */
func canGetString (s string, t string) bool {
    i, j := 0, 0
    for i<len(s) && j<len(t) {
        if s[i] != t[j] {
            i++
            continue
        }
        i, j = i+1, j+1
    }
    return j==len(t)
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.