c*****e
发帖数: 3226 | 1 public class Solution {
class Record {
Record prev;
String cur;
public Record(Record prev, String cur) {
this.prev = prev;
this.cur = cur;
}
}
public List> findLadders(String start, String end, Set<
String> dict) {
List> r = new LinkedList>();
if (start == null || end == null || dict == null || start.length() =
= 0 || start.length() != end.length()) {
return r;
}
Queue p = new LinkedList();
Set used = new TreeSet();
p.add(new Record(null, start));
used.add(start);
while(!p.isEmpty()) {
Queue p2 = new LinkedList();
Set level_used = new TreeSet();
for(Record record: p) {
String cur = record.cur;
for (int i = 0; i < cur.length(); i++) {
String left = cur.substring(0, i);
String right = cur.substring(i+1);
for (char c='a'; c <='z'; c++) {
if (c != cur.charAt(i)) {
String n = left + String.valueOf(c) + right;
if (n.equals(end)) {
List path = new LinkedList();
path.add(end);
Record r0 = record;
while(r0 != null) {
path.add(0, r0.cur);
r0 = r0.prev;
}
r.add(path);
} else if (dict.contains(n) && !used.contains(n)
) {
p2.add(new Record(record, n));
level_used.add(n);
}
}
}
}
}
if (!r.isEmpty()) return r;
p = p2;
used.addAll(level_used);
}
return r;
}
} | s******n
发帖数: 226 | | c*****e
发帖数: 3226 | 3 leetcode 狗屎，
我把建立新的string 换成 这个就过了： String n = replace(cur, i, c);
private String replace(String str, int index, char c) {
StringBuilder sb = new StringBuilder(str);
sb.setCharAt(index, c);
return sb.toString();
}
【在 c*****e 的大作中提到】
: public class Solution {
: class Record {
: Record prev;
: String cur;
:
: public Record(Record prev, String cur) {
: this.prev = prev;
: this.cur = cur;
: }
:
| c*********w
发帖数: 65 | 4 String.substring 的实现在java 1.7里被改了，本来是 constant time,现在是
linear.
和GC有关。
【在 c*****e 的大作中提到】
: leetcode 狗屎，
: 我把建立新的string 换成 这个就过了： String n = replace(cur, i, c);
: private String replace(String str, int index, char c) {
: StringBuilder sb = new StringBuilder(str);
: sb.setCharAt(index, c);
: return sb.toString();
: }
| j******o
发帖数: 4219 | 5 leetcode这种只要最佳解的做法和国人的心态一样。 |
|
