面试题 01.05 一次编辑

Posted on | In
Words count in article: 402 | Reading time ≈ 1

题目

字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。

示例1:

1
2
3
4
输入: 
first = "pale"
second = "ple"
输出: True

示例2：

1
2
3
4
输入: 
first = "pales"
second = "pal"
输出: False

解法

解法一：

双指针

如果两个字符串长度相同，按照顺序比较各个位置上的字符是否相等，不相等的个数超过1，返回false

如果两个字符串长度不相等，同样是遍历两个字符串，但是遇到不相等的情况时，只把长的字符串指针往后移，同时统计不相等的个数，超过1返回false

因为，按照题目限制，如果两个字符串可以一次编辑并且不相等的话只可能是在同位置上替换了一个字符或者新增或者删除了一个字符，所以要把长的往后移。

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public boolean oneEditAway(String first, String second) {
			int len1 = Math.max(first.length(), second.length());
			int len2 = Math.min(first.length(), second.length());
			if (len1 - len2 > 1) {
				return false;
			}

			// first为长字符串，second为短字符串
			if (len1 != first.length()) {
				String tmp = first;
				first = second;
				second = tmp;
			}

			int count = 0;
			// 分两种情况
			if (len1 == len2) {
				for (int i = 0; i < len1; i++) {
					if (first.charAt(i) != second.charAt(i))
						count++;
					if (count > 1)
						return false;
				}
			} else {
				for (int i = 0, j = 0; i < len2; j++) {
					if (count > 1)
						return false;
					if (first.charAt(j) != second.charAt(i)) {
						count++;
						continue;
					}
					i++;
				}
			}
			return true;
		}
0%