【LeetCode】161. One Edit Distance

2022-08-27 10:00:00

Difficulty: Medium

Description

Given two strings S and T, determine if they are both one edit distance apart.

Intuition

同时遍历比较S和T的字符，直至遇到不同的字符：如果S和T的字符个数相同时，跳过不同的那个字符，继续遍历；如果S和T的字符个数相差为1时，跳过较长的字符串的当天字符，继续遍历。如果剩下的字符都相等，那么返回true，其余情况为false。

Solution

	public boolean isOneEditDistance(String s, String t) {

		if(s==null || t==null)

			return false;

		if(s.length()<t.length())

			return isOneEditDistance(t, s);    //学会交换

		int i=0;

		while(i<t.length() && s.charAt(i)==t.charAt(i))  //注意i小于较短字符串的长度

			i++;

		if(s.length()==t.length()) {

			i++;

			while(i<t.length() && s.charAt(i)==t.charAt(i))

				i++;

		}else if(s.length()-t.length()==1){

			while(i<t.length() && s.charAt(i+1)==t.charAt(i))

				i++;

		}else

			return false;

		return i==t.length();

	}

Complexity

Time complexity : O(n)

Space complexity : O(1)

What I've learned

1. 代码第5行，学会交换，仅需要实现S字符串的长度大于T字符串的情况。

More:【目录】LeetCode Java实现

码农公寓