AmbiguousCoordinates [source code]
public class AmbiguousCoordinates {
static
/******************************************************************************/
class Solution {
public List<String> ambiguousCoordinates(String S) {
List<String> res = new ArrayList<> ();
if (S.length () < 3)
return res;
S = S.substring (1, S.length () - 1);
int len = S.length ();
for (int i = 1; i <= len - 1; i++) {
String x = S.substring (0, i), y = S.substring (i);
List<String> left = guess (x), right = guess (y);
if (left.isEmpty () || right.isEmpty ())
continue;
for (String left_word : left) {
for (String right_word : right) {
res.add (String.format ("(%s, %s)", left_word, right_word));
}
}
}
return res;
}
List<String> guess (String s) {
List<String> res = new ArrayList<> ();
if (s.length () == 1) {
res.add (s);
return res;
}
int[] next_nonzero = new int[s.length () + 1];
next_nonzero[s.length ()] = -1;
for (int i = s.length () - 1; i >= 0; i--) {
next_nonzero[i] = s.charAt (i) != '0' ? i : next_nonzero[i + 1];
}
if (s.charAt (0) == '0') {
if (next_nonzero[1] >= 0 && s.charAt (s.length () - 1) != '0') {
res.add ("0." + s.substring (1));
}
} else {
res.add (s);
if (s.charAt (s.length () - 1) != '0') {
for (int i = 1; i < s.length () ; i++) {
if (next_nonzero[i] > 0) {
res.add (s.substring (0, i) + "." + s.substring (i));
}
}
}
}
return res;
}
}
/******************************************************************************/
public static void main(String[] args) {
AmbiguousCoordinates.Solution tester = new AmbiguousCoordinates.Solution();
String[][] inputs = {
{"(123)"}, {"(1, 23)", "(12, 3)", "(1.2, 3)", "(1, 2.3)"},
{"(00011)"}, {"(0.001, 1)", "(0, 0.011)"},
{"(0123)"}, {"(0, 123)", "(0, 12.3)", "(0, 1.23)", "(0.1, 23)", "(0.1, 2.3)", "(0.12, 3)"},
{"(100)"}, {"(10, 0)"},
{"(0010)"}, {"(0.01, 0)"},
{"(0110)"}, {"(0, 110)","(0.1, 10)","(0.11, 0)"},
};
for (int i = 0; i < inputs.length / 2; i++) {
System.out.println (Printer.separator ());
String S = inputs[2 * i][0];
Set<String> ans = new HashSet<> (Arrays.asList (inputs[2 * i + 1])), output = new HashSet<> (tester.ambiguousCoordinates (S));
System.out.printf (
"%s\n%s, expected: %s\n",
S, Printer.wrap (output.toString (), output.equals (ans) ? 92 : 91), ans
);
}
}
}
感觉就是一个写起来很麻烦的backtrack搜索问题, 这个只能慢慢尝试了;
这题因为只要分成两个, 所以感觉代码难度实际上稍微降低了一点, 不是纯粹的加法拆分那种, 什么都不确定的;
不要太general: 这题既然知道没有加法拆分那种搜索那么复杂, 那么这题是不是有更多的特性可以用来降低难度呢?
我们到底有没有必要用搜索来做? 实际上最后既然就是找一个二分的split, 那么何不直接搜索split的位置? 然后检查两边token的正确性就行了; 这样就不用专门去用backtrack的思路去做;
另一个难度是, 比如有一半是123, 那么这里你要考虑, 123, 1.23, 12.3这几种情况都有; 这个如果再把0加进去, 最后代码写起来也挺复杂的;
看了一下题目要求, S的长度很低, 所以对于S的split操作的string效率, 不用太担心; 拆分之后每一半的处理, 应该是更复杂的地方;
public String(char[] value,
int offset,
int count)
java> String s = "abcde"
java.lang.String s = "abcde"
java> char[] chs = s.toCharArray ()
char[] chs = [a, b, c, d, e]
java> new String (chs, 2, 2)
java.lang.String res3 = "cd"
错误两次之后AC了, 总体来说是一个很有意思的题目;
而且我这里在guess函数里面这个类似DP的设计, 我自己也是有点服了我自己的, 今天思路有点快;
另外在计算这个DP cache的时候, 快速想到用NLP dot思路, 也是很厉害;
草稿:
2018-05-01 20:44:27 举例子还是很重要的, 就是要脑子转的快一点, 然后快速的举例子+总结的无限循环的思考过程;
另外这题不知道为什么downvote非常的多;
另外我上面这个算法, left和right是一起先eager的计算完的, 这个是可以优化的, left计算过了如果失败(返回空的), 那么right就不用计算了;
面试的时候如果碰到这题还是挺坑的, 边界情况太多了; 另外回头重新看我自己的这个算法, 实际上冗余逻辑还是挺多的;
比如guess下面的第二个分支, 开头不是0的情况, 只要再判断了最后一位也不是0, 那么就可以随便分了; 里面对于next_nonzero的判断实际上是多余的;
editorial
Approach #1: Cartesian Product [Accepted]
Intuition and Algorithm
For each place to put the comma, we separate the string into two fragments. For example, with a string like "1234", we could separate it into fragments "1" and "234", "12" and "34", or "123" and "4".
Then, for each fragment, we have a choice of where to put the period, to create a list make(...) of choices. For example, "123" could be made into "1.23", "12.3", or "123".
Because of extranneous zeroes, we should ignore possibilities where the part of the fragment to the left of the decimal starts with "0" (unless it is exactly "0"), and ignore possibilities where the part of the fragment to the right of the decimal ends with "0", as these are not allowed.
他这个对于不合法的情况给出了一个明确的界定;
Note that this process could result in an empty answer, such as for the case S = "(000)".
class Solution { //aw
public List<String> ambiguousCoordinates(String S) {
List<String> ans = new ArrayList();
for (int i = 2; i < S.length()-1; ++i)
for (String left: make(S, 1, i))
for (String right: make(S, i, S.length()-1))
ans.add("(" + left + ", " + right + ")");
return ans;
}
public List<String> make(String S, int i, int j) {
// Make on S.substring(i, j)
List<String> ans = new ArrayList();
for (int d = 1; d <= j-i; ++d) {
String left = S.substring(i, i+d);
String right = S.substring(i+d, j);
if ((!left.startsWith("0") || left.equals("0"))
&& !right.endsWith("0"))
ans.add(left + (d < j-i ? "." : "") + right);
}
return ans;
}
}
看他主函数的写法, 实际上是有那个类似shortcircut的优化的: 只有左边成功, 才会去执行右边;
另外你看他这里一个小操作, 他避免了我那样的两次substring: 主函数的split完全只是通过传递index来完成, 最后在make里面需要真的把这个string给做出来的时候, 再substring;
循环变量d用一个offset的形式我不太喜欢, 我还是喜欢用比如d = i..j这样来写比较好; 不过对于这个问题本身来说这个变化不会造成难度;
看他这里: !left.startsWith("0") || left.equals("0"), 这个单看是很难理解的, 这个其实是一个imply的操作: 如果left是0开头, 那么必须整个是0. awice的这些基本功还是真的稳; 他最后这样写整个合法性的判断就相当的简练了;
复杂度是N^3;
有一定的道理; 不过这个sum是怎么计算的? 拆开就行了, 第一项是等差数列, 第二项是一个1^2 + 2^2 + ... + N^2, 这个是多少? 积分吗?
积分是比较好证明的做法; 网上还有更加tricky一点的做法:
UNFINISHED
uwi:
class Solution {
public List<String> ambiguousCoordinates(String S) {
S = S.substring(1, S.length()-1);
int n = S.length();
List<String> ret = new ArrayList<>();
for(int i = 1;i <= n-1;i++){
List<String> va = valids(S.substring(0, i));
List<String> vb = valids(S.substring(i, n));
for(String a : va){
for(String b : vb){
ret.add("(" + a + ", " + b + ")");
}
}
}
return ret;
}
List<String> valids(String s)
{
List<String> ret = new ArrayList<>();
if(valid(s))ret.add(s);
for(int i = 1;i < s.length();i++){
String t = s.substring(0, i) + "." + s.substring(i);
if(valid(t))ret.add(t);
}
return ret;
}
boolean valid(String s)
{
if(s.lastIndexOf("-") > 0)return false;
if(s.equals("-0"))return false;
if(s.startsWith("-")){
s = s.substring(1);
}
if(s.length() == 0)return false;
if(s.indexOf(".") < 0){
if(s.length() > 1 && s.startsWith("0"))return false;
return true;
}else{
String[] sp = s.split("\\.");
if(sp.length < 2)return false;
if(sp[0].length() == 0)return false;
if(sp[0].length() > 1 && sp[0].startsWith("0"))return false;
if(sp[1].endsWith("0"))return false;
return true;
}
}
}
好像不是很乱的样子; 这题我自己的方法虽然自作聪明的认为还不错, 但是可以了解一下discuss里面lee的那个做法, 他的思路其实比我的好; 不过我觉得我这个思路也还行吧;
Problem Description
We had some 2-dimensional coordinates, like "(1, 3)" or "(2, 0.5)". Then, we removed all commas, decimal points, and spaces, and ended up with the string S. Return a list of strings representing all possibilities for what our original coordinates could have been.
Our original representation never had extraneous zeroes, so we never started with numbers like "00", "0.0", "0.00", "1.0", "001", "00.01", or any other number that can be represented with less digits. Also, a decimal point within a number never occurs without at least one digit occuring before it, so we never started with numbers like ".1".
The final answer list can be returned in any order. Also note that all coordinates in the final answer have exactly one space between them (occurring after the comma.)
Example 1:
Input: "(123)"
Output: ["(1, 23)", "(12, 3)", "(1.2, 3)", "(1, 2.3)"]
Example 2:
Input: "(00011)"
Output: ["(0.001, 1)", "(0, 0.011)"]
Explanation:
0.0, 00, 0001 or 00.01 are not allowed.
Example 3:
Input: "(0123)"
Output: ["(0, 123)", "(0, 12.3)", "(0, 1.23)", "(0.1, 23)", "(0.1, 2.3)", "(0.12, 3)"]
Example 4:
Input: "(100)"
Output: [(10, 0)]
Explanation:
1.0 is not allowed.
Note:
- 4 <= S.length <= 12.
- S[0] = "(", S[S.length - 1] = ")", and the other elements in S are digits.
Difficulty:Medium
Total Accepted:750
Total Submissions:1.9K
Contributor:awice
Companies
google
Related Topics
string