Cracking the Coding Interview — 1.5 One AwayCalculate the Hamming difference between two DNA strandsMaking as many unique strings as possible by removing two charactersHackerRank, Cracking the Coding Interview: Arrays - Left RotationInterview Coding Challeng for iOS Part 1 - the Static Objective-C LibraryFind the Thief - Coding Challenge - JavaScript ImplementationFind the smallest number in the first array that is not in the second oneCracking the Coding Interview: “Problem 1.5. One Away”Cracking the coding interview 1.7 - Rotate matrix by 90 degreesCracking the Coding Interview - 4.1 Graph TraversalCracking the code interview: Problem 1 .6 basic string compression

How to loop for 3 times in bash script when docker push fails?

C program to parse source code of another language

Combining latex input and sed

How did the hit man miss?

How to ask for a LinkedIn endorsement?

Confirming the Identity of a (Friendly) Reviewer After the Reviews

Constructive proof of existence of free algebras for infinitary equational theories

Integer Lists of Noah

definition of "percentile"

Good resources for solving techniques (Metaheuristics, MILP, CP etc)

How to md5 a list of filepaths contained in a file?

Received a dinner invitation through my employer's email, is it ok to attend?

Why are all my yellow 2V/20mA LEDs burning out with 330k Ohm resistor?

Modulus Operandi

Is a request to book a business flight ticket for a graduate student an unreasonable one?

For a hashing function like MD5, how similar can two plaintext strings be and still generate the same hash?

Would dual wielding daggers be a viable choice for a covert bodyguard?

Optimization terminology: "Exact" v. "Approximate"

How can I calculate the sum of 2 random dice out of a 3d6 pool in AnyDice?

How is angular momentum conserved for the orbiting body if the centripetal force disappears?

Why did Harry Potter get a bedroom?

Meat Substitutes

What does (void *)1 mean

Is a 10th-level Transmutation wizard considered a shapechanger for the purpose of effects such as Moonbeam?



Cracking the Coding Interview — 1.5 One Away


Calculate the Hamming difference between two DNA strandsMaking as many unique strings as possible by removing two charactersHackerRank, Cracking the Coding Interview: Arrays - Left RotationInterview Coding Challeng for iOS Part 1 - the Static Objective-C LibraryFind the Thief - Coding Challenge - JavaScript ImplementationFind the smallest number in the first array that is not in the second oneCracking the Coding Interview: “Problem 1.5. One Away”Cracking the coding interview 1.7 - Rotate matrix by 90 degreesCracking the Coding Interview - 4.1 Graph TraversalCracking the code interview: Problem 1 .6 basic string compression






.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;








7












$begingroup$


I would like to know any suggestions about to improve my code solution and your rating of my approach to the problem, I based my code on the fact that if the strings have different length removing one character from the longer string is equal to add one character to the shorter one.



Description




One away : There are three types of edits that can be performed on
strings: insert a character, remove a character and replace a
character. Given two strings, write a function to check if they are
one edit (or zero edits) away.




#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int helper_one_way(const char *str1, const char * str2,
size_t len1, size_t flag)
size_t nchars = 0;
size_t i, j;

for (i = 0, j = 0; i < len1; ++i, ++j)
if (str1[i] != str2[j])
if (++nchars > 1) return 0;
if (flag && i) --i;


return 1;


/* check if str1 can be obtained from string2 adding, deleting, removing
* at last one char */
int one_way(const char *str1, const char *str2)
size_t len1 = strlen(str1), len2 = strlen(str2);
size_t diff = abs(len1 - len2);

if (diff > 1) return 0;
if (!diff) return helper_one_way(str1, str2, len1, 0);
if (len1 > len2) return helper_one_way(str2, str1, len2, 1);
return helper_one_way(str1, str2, len1, 1);


int main(void)
printf("%dn", one_way("pale", "ple"));
printf("%dn", one_way("pales", "pale"));
printf("%dn", one_way("pale", "bale"));
printf("%dn", one_way("pale", "bake"));
return 0;










share|improve this question











$endgroup$


















    7












    $begingroup$


    I would like to know any suggestions about to improve my code solution and your rating of my approach to the problem, I based my code on the fact that if the strings have different length removing one character from the longer string is equal to add one character to the shorter one.



    Description




    One away : There are three types of edits that can be performed on
    strings: insert a character, remove a character and replace a
    character. Given two strings, write a function to check if they are
    one edit (or zero edits) away.




    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>

    static int helper_one_way(const char *str1, const char * str2,
    size_t len1, size_t flag)
    size_t nchars = 0;
    size_t i, j;

    for (i = 0, j = 0; i < len1; ++i, ++j)
    if (str1[i] != str2[j])
    if (++nchars > 1) return 0;
    if (flag && i) --i;


    return 1;


    /* check if str1 can be obtained from string2 adding, deleting, removing
    * at last one char */
    int one_way(const char *str1, const char *str2)
    size_t len1 = strlen(str1), len2 = strlen(str2);
    size_t diff = abs(len1 - len2);

    if (diff > 1) return 0;
    if (!diff) return helper_one_way(str1, str2, len1, 0);
    if (len1 > len2) return helper_one_way(str2, str1, len2, 1);
    return helper_one_way(str1, str2, len1, 1);


    int main(void)
    printf("%dn", one_way("pale", "ple"));
    printf("%dn", one_way("pales", "pale"));
    printf("%dn", one_way("pale", "bale"));
    printf("%dn", one_way("pale", "bake"));
    return 0;










    share|improve this question











    $endgroup$














      7












      7








      7





      $begingroup$


      I would like to know any suggestions about to improve my code solution and your rating of my approach to the problem, I based my code on the fact that if the strings have different length removing one character from the longer string is equal to add one character to the shorter one.



      Description




      One away : There are three types of edits that can be performed on
      strings: insert a character, remove a character and replace a
      character. Given two strings, write a function to check if they are
      one edit (or zero edits) away.




      #include <stdio.h>
      #include <stdlib.h>
      #include <string.h>

      static int helper_one_way(const char *str1, const char * str2,
      size_t len1, size_t flag)
      size_t nchars = 0;
      size_t i, j;

      for (i = 0, j = 0; i < len1; ++i, ++j)
      if (str1[i] != str2[j])
      if (++nchars > 1) return 0;
      if (flag && i) --i;


      return 1;


      /* check if str1 can be obtained from string2 adding, deleting, removing
      * at last one char */
      int one_way(const char *str1, const char *str2)
      size_t len1 = strlen(str1), len2 = strlen(str2);
      size_t diff = abs(len1 - len2);

      if (diff > 1) return 0;
      if (!diff) return helper_one_way(str1, str2, len1, 0);
      if (len1 > len2) return helper_one_way(str2, str1, len2, 1);
      return helper_one_way(str1, str2, len1, 1);


      int main(void)
      printf("%dn", one_way("pale", "ple"));
      printf("%dn", one_way("pales", "pale"));
      printf("%dn", one_way("pale", "bale"));
      printf("%dn", one_way("pale", "bake"));
      return 0;










      share|improve this question











      $endgroup$




      I would like to know any suggestions about to improve my code solution and your rating of my approach to the problem, I based my code on the fact that if the strings have different length removing one character from the longer string is equal to add one character to the shorter one.



      Description




      One away : There are three types of edits that can be performed on
      strings: insert a character, remove a character and replace a
      character. Given two strings, write a function to check if they are
      one edit (or zero edits) away.




      #include <stdio.h>
      #include <stdlib.h>
      #include <string.h>

      static int helper_one_way(const char *str1, const char * str2,
      size_t len1, size_t flag)
      size_t nchars = 0;
      size_t i, j;

      for (i = 0, j = 0; i < len1; ++i, ++j)
      if (str1[i] != str2[j])
      if (++nchars > 1) return 0;
      if (flag && i) --i;


      return 1;


      /* check if str1 can be obtained from string2 adding, deleting, removing
      * at last one char */
      int one_way(const char *str1, const char *str2)
      size_t len1 = strlen(str1), len2 = strlen(str2);
      size_t diff = abs(len1 - len2);

      if (diff > 1) return 0;
      if (!diff) return helper_one_way(str1, str2, len1, 0);
      if (len1 > len2) return helper_one_way(str2, str1, len2, 1);
      return helper_one_way(str1, str2, len1, 1);


      int main(void)
      printf("%dn", one_way("pale", "ple"));
      printf("%dn", one_way("pales", "pale"));
      printf("%dn", one_way("pale", "bale"));
      printf("%dn", one_way("pale", "bake"));
      return 0;







      algorithm c programming-challenge edit-distance c89






      share|improve this question















      share|improve this question













      share|improve this question




      share|improve this question








      edited 8 hours ago









      200_success

      134k21 gold badges171 silver badges441 bronze badges




      134k21 gold badges171 silver badges441 bronze badges










      asked 9 hours ago









      dariogithubdariogithub

      543 bronze badges




      543 bronze badges




















          3 Answers
          3






          active

          oldest

          votes


















          2












          $begingroup$

          This is more of a suggestion on substance than a review of the code style; I'll leave that for other reviewers.



          Your solution looks pretty good to me. I think you could streamline it a bit by doing it all in one shot, without checking the length of the strings first. For example:



          int one_way(const char *a, const char *b)



          I guess it's pretty self-explanatory, and similar enough to what you were doing. You can test it out here: https://www.onlinegdb.com/SkfktK7WS






          share|improve this answer










          New contributor



          user11536834 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
          Check out our Code of Conduct.





          $endgroup$












          • $begingroup$
            Try "aa" and "ba". Sorry I gave you the wrong test-case.
            $endgroup$
            – Deduplicator
            1 hour ago







          • 1




            $begingroup$
            @Deduplicator thanks for catching that, had a feeling this wasn't quite complete. I think you could probably add something like this to let the other iterator "catch up" after this situation happens: beta.pastie.org/iH3jbXzFRKhh ... but it's not exactly model clean code at this point. Will think about this a bit and edit or remove this answer later.
            $endgroup$
            – user11536834
            1 hour ago










          • $begingroup$
            I took a different approach which also resulted in a single traversal.
            $endgroup$
            – Deduplicator
            57 mins ago


















          2












          $begingroup$

          Generally nice code: easy to read, good use of const char* for the string arguments.




          It's great that we have unit tests; we can improve them by making them self-checking:



          /* return number of test failures (0 or 1) */
          int test_one_away(const char *str1, const char *str2, int expected)

          const int actual = one_way(str1, str2);
          if (actual == expected)
          return 0;
          fprintf(stderr, "one_way "%s", "%s" expected %d but got %dn",
          str1, str2, expected, actual);
          return 1;



          int main(void)

          return
          + test_one_away("pale", "ple", 1)
          + test_one_away("pales", "pale", 1)
          + test_one_away("pale", "bale", 1)
          + test_one_away("pale", "bake", 0);




          We should add some more tests. Here's a test that exposes a bug in the code:



           + test_one_away("pale", "ale", 1)


          This is because we don't accept deletion of the first character:




           if (flag && i) --i;



          The fix is to remove the second part of the condition (remember, unsigned overflow is well-defined, and will exactly match the ++i in the loop increment):



           if (flag) --i;



          I'm not sure why flag needs to be a size_t; include <stdbool.h> and make it a bool. It also needs a better name; I had to look to the call site to understand what it's for (it seems that a true value means that we're looking for a deletion rather than a replacement).




          The conditions in the wrapper function could be expressed more clearly with a single switch on the difference in length:



          /* check if str1 can be obtained from string2 adding, deleting, removing
          * at last one char */
          bool one_way(const char *str1, const char *str2)


          size_t len1 = strlen(str1);
          size_t len2 = strlen(str2);

          switch (len2 - len1)
          case (size_t)-1: return helper_one_way(str2, str1, len2, true);
          case 0: return helper_one_way(str1, str2, len1, false);
          case 1: return helper_one_way(str1, str2, len2, true);
          default: return false;





          We don't need to pass the length to helper_one_way, because it can simply stop when it reaches the terminating null char:



           for (i = 0, j = 0; str1[i]; ++i, ++j) {



          Given that we're iterating over strings, it's more idiomatic to use a char pointer than to repeatedly index into the string (though a good compiler ought to generate the same code):



          static bool helper_one_way(const char *a, const char *b,
          bool allow_deletion)

          size_t nchars = 0;
          while (*a)
          if (*a++ != *b++)
          if (++nchars > 1) return false;
          if (allow_deletion) --b;


          return true;




          Finally: the name - should one_way be spelt one_away?




          Modified code



          Applying the above suggestions, we get:



          #include <stdbool.h>
          #include <string.h>

          static bool helper_one_away(const char *a, const char *b,
          bool allow_deletion)

          size_t nchars = 0;
          while (*a)
          if (*a++ != *b++)
          if (++nchars > 1) return false;
          if (allow_deletion) --b;


          return true;


          /* Return true if a can be obtained from string2 by adding,
          deleting, or removing at most one character */
          bool one_away(const char *a, const char *b)

          switch (strlen(a) - strlen(b))
          case (size_t)-1: return helper_one_away(b, a, true);
          case 0: return helper_one_away(a, b, false);
          case 1: return helper_one_away(a, b, true);
          default: return false;




          /* Test code */

          #include <stdio.h>

          /* return number of test failures (0 or 1) */
          static int test_one_away(const char *a, const char *b,
          bool expected)

          const int actual = one_away(a, b);
          if (actual == expected)
          return 0;
          fprintf(stderr, "one_away "%s", "%s" expected %d but got %dn",
          a, b, expected, actual);
          return 1;


          int main(void)

          return
          + test_one_away("", "", true)
          + test_one_away("", "a", true)
          + test_one_away("pale", "", false)
          + test_one_away("pale", "le", false)
          + test_one_away("pale", "ale", true)
          + test_one_away("pale", "pale", true)
          + test_one_away("pale", "pal", true)
          + test_one_away("pale", "pa", false)
          + test_one_away("pale", "ple", true)
          + test_one_away("ple", "pale", true)
          + test_one_away("pales", "pale", true)
          + test_one_away("pale", "bale", true)
          + test_one_away("pale", "bake", false);






          share|improve this answer









          $endgroup$












          • $begingroup$
            bool makes its debut in C99 after including <stdbool.h>. OP cannot use it.
            $endgroup$
            – Deduplicator
            3 hours ago


















          0












          $begingroup$

          1. Using a size_t for a boolean flag, and calling it flag, is nearly an obfuscation. Use int pre-C99 and call it something descriptive like substitute.


          2. strlen() is likely a waste, though it makes describing the algorithm easier. Try to do without the additional iteration.


          3. Getting the length of the longest common prefix looks like a well-defined task which can be extracted, and a useful building-block. Do so.


          4. one_way, one_away, or one_microsoft_way? Having a properly-spelled correctly-selected name is Always very important.



          5. Change to a single-traversal algorithm:



            Remove he common prefix.



            Measuring the common prefix without the first characters is quite instructive.



            With x and y different from a, call n = strlen_common(++a, ++b):




            1. At most one substitution at the start:



              xaaaabcde
              yaaaabcde


              Result n == 8, a[n] == b[n].




            2. Deletion from the first:



              xaaaabcde
              aaaabcde


              n == 3, strcmp(a + n, b + n - 1) != 0



            3. Same way for deletion from second.



          The modified code (also live on coliru):



          size_t strlen_common(const char* a, const char* b) 
          size_t r = 0;
          while (*a && *a++ == *b++)
          ++r;
          return r;


          int one_away(const char* a, const char* b) !b[1];
          if (!*b)
          return !a[1];
          n = strlen_common(++a, ++b);
          return a[n] == b[n]






          share|improve this answer











          $endgroup$















            Your Answer






            StackExchange.ifUsing("editor", function ()
            StackExchange.using("externalEditor", function ()
            StackExchange.using("snippets", function ()
            StackExchange.snippets.init();
            );
            );
            , "code-snippets");

            StackExchange.ready(function()
            var channelOptions =
            tags: "".split(" "),
            id: "196"
            ;
            initTagRenderer("".split(" "), "".split(" "), channelOptions);

            StackExchange.using("externalEditor", function()
            // Have to fire editor after snippets, if snippets enabled
            if (StackExchange.settings.snippets.snippetsEnabled)
            StackExchange.using("snippets", function()
            createEditor();
            );

            else
            createEditor();

            );

            function createEditor()
            StackExchange.prepareEditor(
            heartbeatType: 'answer',
            autoActivateHeartbeat: false,
            convertImagesToLinks: false,
            noModals: true,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: null,
            bindNavPrevention: true,
            postfix: "",
            imageUploader:
            brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
            contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
            allowUrls: true
            ,
            onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            );



            );













            draft saved

            draft discarded


















            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f223872%2fcracking-the-coding-interview-1-5-one-away%23new-answer', 'question_page');

            );

            Post as a guest















            Required, but never shown

























            3 Answers
            3






            active

            oldest

            votes








            3 Answers
            3






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes









            2












            $begingroup$

            This is more of a suggestion on substance than a review of the code style; I'll leave that for other reviewers.



            Your solution looks pretty good to me. I think you could streamline it a bit by doing it all in one shot, without checking the length of the strings first. For example:



            int one_way(const char *a, const char *b)



            I guess it's pretty self-explanatory, and similar enough to what you were doing. You can test it out here: https://www.onlinegdb.com/SkfktK7WS






            share|improve this answer










            New contributor



            user11536834 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
            Check out our Code of Conduct.





            $endgroup$












            • $begingroup$
              Try "aa" and "ba". Sorry I gave you the wrong test-case.
              $endgroup$
              – Deduplicator
              1 hour ago







            • 1




              $begingroup$
              @Deduplicator thanks for catching that, had a feeling this wasn't quite complete. I think you could probably add something like this to let the other iterator "catch up" after this situation happens: beta.pastie.org/iH3jbXzFRKhh ... but it's not exactly model clean code at this point. Will think about this a bit and edit or remove this answer later.
              $endgroup$
              – user11536834
              1 hour ago










            • $begingroup$
              I took a different approach which also resulted in a single traversal.
              $endgroup$
              – Deduplicator
              57 mins ago















            2












            $begingroup$

            This is more of a suggestion on substance than a review of the code style; I'll leave that for other reviewers.



            Your solution looks pretty good to me. I think you could streamline it a bit by doing it all in one shot, without checking the length of the strings first. For example:



            int one_way(const char *a, const char *b)



            I guess it's pretty self-explanatory, and similar enough to what you were doing. You can test it out here: https://www.onlinegdb.com/SkfktK7WS






            share|improve this answer










            New contributor



            user11536834 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
            Check out our Code of Conduct.





            $endgroup$












            • $begingroup$
              Try "aa" and "ba". Sorry I gave you the wrong test-case.
              $endgroup$
              – Deduplicator
              1 hour ago







            • 1




              $begingroup$
              @Deduplicator thanks for catching that, had a feeling this wasn't quite complete. I think you could probably add something like this to let the other iterator "catch up" after this situation happens: beta.pastie.org/iH3jbXzFRKhh ... but it's not exactly model clean code at this point. Will think about this a bit and edit or remove this answer later.
              $endgroup$
              – user11536834
              1 hour ago










            • $begingroup$
              I took a different approach which also resulted in a single traversal.
              $endgroup$
              – Deduplicator
              57 mins ago













            2












            2








            2





            $begingroup$

            This is more of a suggestion on substance than a review of the code style; I'll leave that for other reviewers.



            Your solution looks pretty good to me. I think you could streamline it a bit by doing it all in one shot, without checking the length of the strings first. For example:



            int one_way(const char *a, const char *b)



            I guess it's pretty self-explanatory, and similar enough to what you were doing. You can test it out here: https://www.onlinegdb.com/SkfktK7WS






            share|improve this answer










            New contributor



            user11536834 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
            Check out our Code of Conduct.





            $endgroup$



            This is more of a suggestion on substance than a review of the code style; I'll leave that for other reviewers.



            Your solution looks pretty good to me. I think you could streamline it a bit by doing it all in one shot, without checking the length of the strings first. For example:



            int one_way(const char *a, const char *b)



            I guess it's pretty self-explanatory, and similar enough to what you were doing. You can test it out here: https://www.onlinegdb.com/SkfktK7WS







            share|improve this answer










            New contributor



            user11536834 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
            Check out our Code of Conduct.








            share|improve this answer



            share|improve this answer








            edited 7 hours ago





















            New contributor



            user11536834 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
            Check out our Code of Conduct.








            answered 8 hours ago









            user11536834user11536834

            1886 bronze badges




            1886 bronze badges




            New contributor



            user11536834 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
            Check out our Code of Conduct.




            New contributor




            user11536834 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
            Check out our Code of Conduct.













            • $begingroup$
              Try "aa" and "ba". Sorry I gave you the wrong test-case.
              $endgroup$
              – Deduplicator
              1 hour ago







            • 1




              $begingroup$
              @Deduplicator thanks for catching that, had a feeling this wasn't quite complete. I think you could probably add something like this to let the other iterator "catch up" after this situation happens: beta.pastie.org/iH3jbXzFRKhh ... but it's not exactly model clean code at this point. Will think about this a bit and edit or remove this answer later.
              $endgroup$
              – user11536834
              1 hour ago










            • $begingroup$
              I took a different approach which also resulted in a single traversal.
              $endgroup$
              – Deduplicator
              57 mins ago
















            • $begingroup$
              Try "aa" and "ba". Sorry I gave you the wrong test-case.
              $endgroup$
              – Deduplicator
              1 hour ago







            • 1




              $begingroup$
              @Deduplicator thanks for catching that, had a feeling this wasn't quite complete. I think you could probably add something like this to let the other iterator "catch up" after this situation happens: beta.pastie.org/iH3jbXzFRKhh ... but it's not exactly model clean code at this point. Will think about this a bit and edit or remove this answer later.
              $endgroup$
              – user11536834
              1 hour ago










            • $begingroup$
              I took a different approach which also resulted in a single traversal.
              $endgroup$
              – Deduplicator
              57 mins ago















            $begingroup$
            Try "aa" and "ba". Sorry I gave you the wrong test-case.
            $endgroup$
            – Deduplicator
            1 hour ago





            $begingroup$
            Try "aa" and "ba". Sorry I gave you the wrong test-case.
            $endgroup$
            – Deduplicator
            1 hour ago





            1




            1




            $begingroup$
            @Deduplicator thanks for catching that, had a feeling this wasn't quite complete. I think you could probably add something like this to let the other iterator "catch up" after this situation happens: beta.pastie.org/iH3jbXzFRKhh ... but it's not exactly model clean code at this point. Will think about this a bit and edit or remove this answer later.
            $endgroup$
            – user11536834
            1 hour ago




            $begingroup$
            @Deduplicator thanks for catching that, had a feeling this wasn't quite complete. I think you could probably add something like this to let the other iterator "catch up" after this situation happens: beta.pastie.org/iH3jbXzFRKhh ... but it's not exactly model clean code at this point. Will think about this a bit and edit or remove this answer later.
            $endgroup$
            – user11536834
            1 hour ago












            $begingroup$
            I took a different approach which also resulted in a single traversal.
            $endgroup$
            – Deduplicator
            57 mins ago




            $begingroup$
            I took a different approach which also resulted in a single traversal.
            $endgroup$
            – Deduplicator
            57 mins ago













            2












            $begingroup$

            Generally nice code: easy to read, good use of const char* for the string arguments.




            It's great that we have unit tests; we can improve them by making them self-checking:



            /* return number of test failures (0 or 1) */
            int test_one_away(const char *str1, const char *str2, int expected)

            const int actual = one_way(str1, str2);
            if (actual == expected)
            return 0;
            fprintf(stderr, "one_way "%s", "%s" expected %d but got %dn",
            str1, str2, expected, actual);
            return 1;



            int main(void)

            return
            + test_one_away("pale", "ple", 1)
            + test_one_away("pales", "pale", 1)
            + test_one_away("pale", "bale", 1)
            + test_one_away("pale", "bake", 0);




            We should add some more tests. Here's a test that exposes a bug in the code:



             + test_one_away("pale", "ale", 1)


            This is because we don't accept deletion of the first character:




             if (flag && i) --i;



            The fix is to remove the second part of the condition (remember, unsigned overflow is well-defined, and will exactly match the ++i in the loop increment):



             if (flag) --i;



            I'm not sure why flag needs to be a size_t; include <stdbool.h> and make it a bool. It also needs a better name; I had to look to the call site to understand what it's for (it seems that a true value means that we're looking for a deletion rather than a replacement).




            The conditions in the wrapper function could be expressed more clearly with a single switch on the difference in length:



            /* check if str1 can be obtained from string2 adding, deleting, removing
            * at last one char */
            bool one_way(const char *str1, const char *str2)


            size_t len1 = strlen(str1);
            size_t len2 = strlen(str2);

            switch (len2 - len1)
            case (size_t)-1: return helper_one_way(str2, str1, len2, true);
            case 0: return helper_one_way(str1, str2, len1, false);
            case 1: return helper_one_way(str1, str2, len2, true);
            default: return false;





            We don't need to pass the length to helper_one_way, because it can simply stop when it reaches the terminating null char:



             for (i = 0, j = 0; str1[i]; ++i, ++j) {



            Given that we're iterating over strings, it's more idiomatic to use a char pointer than to repeatedly index into the string (though a good compiler ought to generate the same code):



            static bool helper_one_way(const char *a, const char *b,
            bool allow_deletion)

            size_t nchars = 0;
            while (*a)
            if (*a++ != *b++)
            if (++nchars > 1) return false;
            if (allow_deletion) --b;


            return true;




            Finally: the name - should one_way be spelt one_away?




            Modified code



            Applying the above suggestions, we get:



            #include <stdbool.h>
            #include <string.h>

            static bool helper_one_away(const char *a, const char *b,
            bool allow_deletion)

            size_t nchars = 0;
            while (*a)
            if (*a++ != *b++)
            if (++nchars > 1) return false;
            if (allow_deletion) --b;


            return true;


            /* Return true if a can be obtained from string2 by adding,
            deleting, or removing at most one character */
            bool one_away(const char *a, const char *b)

            switch (strlen(a) - strlen(b))
            case (size_t)-1: return helper_one_away(b, a, true);
            case 0: return helper_one_away(a, b, false);
            case 1: return helper_one_away(a, b, true);
            default: return false;




            /* Test code */

            #include <stdio.h>

            /* return number of test failures (0 or 1) */
            static int test_one_away(const char *a, const char *b,
            bool expected)

            const int actual = one_away(a, b);
            if (actual == expected)
            return 0;
            fprintf(stderr, "one_away "%s", "%s" expected %d but got %dn",
            a, b, expected, actual);
            return 1;


            int main(void)

            return
            + test_one_away("", "", true)
            + test_one_away("", "a", true)
            + test_one_away("pale", "", false)
            + test_one_away("pale", "le", false)
            + test_one_away("pale", "ale", true)
            + test_one_away("pale", "pale", true)
            + test_one_away("pale", "pal", true)
            + test_one_away("pale", "pa", false)
            + test_one_away("pale", "ple", true)
            + test_one_away("ple", "pale", true)
            + test_one_away("pales", "pale", true)
            + test_one_away("pale", "bale", true)
            + test_one_away("pale", "bake", false);






            share|improve this answer









            $endgroup$












            • $begingroup$
              bool makes its debut in C99 after including <stdbool.h>. OP cannot use it.
              $endgroup$
              – Deduplicator
              3 hours ago















            2












            $begingroup$

            Generally nice code: easy to read, good use of const char* for the string arguments.




            It's great that we have unit tests; we can improve them by making them self-checking:



            /* return number of test failures (0 or 1) */
            int test_one_away(const char *str1, const char *str2, int expected)

            const int actual = one_way(str1, str2);
            if (actual == expected)
            return 0;
            fprintf(stderr, "one_way "%s", "%s" expected %d but got %dn",
            str1, str2, expected, actual);
            return 1;



            int main(void)

            return
            + test_one_away("pale", "ple", 1)
            + test_one_away("pales", "pale", 1)
            + test_one_away("pale", "bale", 1)
            + test_one_away("pale", "bake", 0);




            We should add some more tests. Here's a test that exposes a bug in the code:



             + test_one_away("pale", "ale", 1)


            This is because we don't accept deletion of the first character:




             if (flag && i) --i;



            The fix is to remove the second part of the condition (remember, unsigned overflow is well-defined, and will exactly match the ++i in the loop increment):



             if (flag) --i;



            I'm not sure why flag needs to be a size_t; include <stdbool.h> and make it a bool. It also needs a better name; I had to look to the call site to understand what it's for (it seems that a true value means that we're looking for a deletion rather than a replacement).




            The conditions in the wrapper function could be expressed more clearly with a single switch on the difference in length:



            /* check if str1 can be obtained from string2 adding, deleting, removing
            * at last one char */
            bool one_way(const char *str1, const char *str2)


            size_t len1 = strlen(str1);
            size_t len2 = strlen(str2);

            switch (len2 - len1)
            case (size_t)-1: return helper_one_way(str2, str1, len2, true);
            case 0: return helper_one_way(str1, str2, len1, false);
            case 1: return helper_one_way(str1, str2, len2, true);
            default: return false;





            We don't need to pass the length to helper_one_way, because it can simply stop when it reaches the terminating null char:



             for (i = 0, j = 0; str1[i]; ++i, ++j) {



            Given that we're iterating over strings, it's more idiomatic to use a char pointer than to repeatedly index into the string (though a good compiler ought to generate the same code):



            static bool helper_one_way(const char *a, const char *b,
            bool allow_deletion)

            size_t nchars = 0;
            while (*a)
            if (*a++ != *b++)
            if (++nchars > 1) return false;
            if (allow_deletion) --b;


            return true;




            Finally: the name - should one_way be spelt one_away?




            Modified code



            Applying the above suggestions, we get:



            #include <stdbool.h>
            #include <string.h>

            static bool helper_one_away(const char *a, const char *b,
            bool allow_deletion)

            size_t nchars = 0;
            while (*a)
            if (*a++ != *b++)
            if (++nchars > 1) return false;
            if (allow_deletion) --b;


            return true;


            /* Return true if a can be obtained from string2 by adding,
            deleting, or removing at most one character */
            bool one_away(const char *a, const char *b)

            switch (strlen(a) - strlen(b))
            case (size_t)-1: return helper_one_away(b, a, true);
            case 0: return helper_one_away(a, b, false);
            case 1: return helper_one_away(a, b, true);
            default: return false;




            /* Test code */

            #include <stdio.h>

            /* return number of test failures (0 or 1) */
            static int test_one_away(const char *a, const char *b,
            bool expected)

            const int actual = one_away(a, b);
            if (actual == expected)
            return 0;
            fprintf(stderr, "one_away "%s", "%s" expected %d but got %dn",
            a, b, expected, actual);
            return 1;


            int main(void)

            return
            + test_one_away("", "", true)
            + test_one_away("", "a", true)
            + test_one_away("pale", "", false)
            + test_one_away("pale", "le", false)
            + test_one_away("pale", "ale", true)
            + test_one_away("pale", "pale", true)
            + test_one_away("pale", "pal", true)
            + test_one_away("pale", "pa", false)
            + test_one_away("pale", "ple", true)
            + test_one_away("ple", "pale", true)
            + test_one_away("pales", "pale", true)
            + test_one_away("pale", "bale", true)
            + test_one_away("pale", "bake", false);






            share|improve this answer









            $endgroup$












            • $begingroup$
              bool makes its debut in C99 after including <stdbool.h>. OP cannot use it.
              $endgroup$
              – Deduplicator
              3 hours ago













            2












            2








            2





            $begingroup$

            Generally nice code: easy to read, good use of const char* for the string arguments.




            It's great that we have unit tests; we can improve them by making them self-checking:



            /* return number of test failures (0 or 1) */
            int test_one_away(const char *str1, const char *str2, int expected)

            const int actual = one_way(str1, str2);
            if (actual == expected)
            return 0;
            fprintf(stderr, "one_way "%s", "%s" expected %d but got %dn",
            str1, str2, expected, actual);
            return 1;



            int main(void)

            return
            + test_one_away("pale", "ple", 1)
            + test_one_away("pales", "pale", 1)
            + test_one_away("pale", "bale", 1)
            + test_one_away("pale", "bake", 0);




            We should add some more tests. Here's a test that exposes a bug in the code:



             + test_one_away("pale", "ale", 1)


            This is because we don't accept deletion of the first character:




             if (flag && i) --i;



            The fix is to remove the second part of the condition (remember, unsigned overflow is well-defined, and will exactly match the ++i in the loop increment):



             if (flag) --i;



            I'm not sure why flag needs to be a size_t; include <stdbool.h> and make it a bool. It also needs a better name; I had to look to the call site to understand what it's for (it seems that a true value means that we're looking for a deletion rather than a replacement).




            The conditions in the wrapper function could be expressed more clearly with a single switch on the difference in length:



            /* check if str1 can be obtained from string2 adding, deleting, removing
            * at last one char */
            bool one_way(const char *str1, const char *str2)


            size_t len1 = strlen(str1);
            size_t len2 = strlen(str2);

            switch (len2 - len1)
            case (size_t)-1: return helper_one_way(str2, str1, len2, true);
            case 0: return helper_one_way(str1, str2, len1, false);
            case 1: return helper_one_way(str1, str2, len2, true);
            default: return false;





            We don't need to pass the length to helper_one_way, because it can simply stop when it reaches the terminating null char:



             for (i = 0, j = 0; str1[i]; ++i, ++j) {



            Given that we're iterating over strings, it's more idiomatic to use a char pointer than to repeatedly index into the string (though a good compiler ought to generate the same code):



            static bool helper_one_way(const char *a, const char *b,
            bool allow_deletion)

            size_t nchars = 0;
            while (*a)
            if (*a++ != *b++)
            if (++nchars > 1) return false;
            if (allow_deletion) --b;


            return true;




            Finally: the name - should one_way be spelt one_away?




            Modified code



            Applying the above suggestions, we get:



            #include <stdbool.h>
            #include <string.h>

            static bool helper_one_away(const char *a, const char *b,
            bool allow_deletion)

            size_t nchars = 0;
            while (*a)
            if (*a++ != *b++)
            if (++nchars > 1) return false;
            if (allow_deletion) --b;


            return true;


            /* Return true if a can be obtained from string2 by adding,
            deleting, or removing at most one character */
            bool one_away(const char *a, const char *b)

            switch (strlen(a) - strlen(b))
            case (size_t)-1: return helper_one_away(b, a, true);
            case 0: return helper_one_away(a, b, false);
            case 1: return helper_one_away(a, b, true);
            default: return false;




            /* Test code */

            #include <stdio.h>

            /* return number of test failures (0 or 1) */
            static int test_one_away(const char *a, const char *b,
            bool expected)

            const int actual = one_away(a, b);
            if (actual == expected)
            return 0;
            fprintf(stderr, "one_away "%s", "%s" expected %d but got %dn",
            a, b, expected, actual);
            return 1;


            int main(void)

            return
            + test_one_away("", "", true)
            + test_one_away("", "a", true)
            + test_one_away("pale", "", false)
            + test_one_away("pale", "le", false)
            + test_one_away("pale", "ale", true)
            + test_one_away("pale", "pale", true)
            + test_one_away("pale", "pal", true)
            + test_one_away("pale", "pa", false)
            + test_one_away("pale", "ple", true)
            + test_one_away("ple", "pale", true)
            + test_one_away("pales", "pale", true)
            + test_one_away("pale", "bale", true)
            + test_one_away("pale", "bake", false);






            share|improve this answer









            $endgroup$



            Generally nice code: easy to read, good use of const char* for the string arguments.




            It's great that we have unit tests; we can improve them by making them self-checking:



            /* return number of test failures (0 or 1) */
            int test_one_away(const char *str1, const char *str2, int expected)

            const int actual = one_way(str1, str2);
            if (actual == expected)
            return 0;
            fprintf(stderr, "one_way "%s", "%s" expected %d but got %dn",
            str1, str2, expected, actual);
            return 1;



            int main(void)

            return
            + test_one_away("pale", "ple", 1)
            + test_one_away("pales", "pale", 1)
            + test_one_away("pale", "bale", 1)
            + test_one_away("pale", "bake", 0);




            We should add some more tests. Here's a test that exposes a bug in the code:



             + test_one_away("pale", "ale", 1)


            This is because we don't accept deletion of the first character:




             if (flag && i) --i;



            The fix is to remove the second part of the condition (remember, unsigned overflow is well-defined, and will exactly match the ++i in the loop increment):



             if (flag) --i;



            I'm not sure why flag needs to be a size_t; include <stdbool.h> and make it a bool. It also needs a better name; I had to look to the call site to understand what it's for (it seems that a true value means that we're looking for a deletion rather than a replacement).




            The conditions in the wrapper function could be expressed more clearly with a single switch on the difference in length:



            /* check if str1 can be obtained from string2 adding, deleting, removing
            * at last one char */
            bool one_way(const char *str1, const char *str2)


            size_t len1 = strlen(str1);
            size_t len2 = strlen(str2);

            switch (len2 - len1)
            case (size_t)-1: return helper_one_way(str2, str1, len2, true);
            case 0: return helper_one_way(str1, str2, len1, false);
            case 1: return helper_one_way(str1, str2, len2, true);
            default: return false;





            We don't need to pass the length to helper_one_way, because it can simply stop when it reaches the terminating null char:



             for (i = 0, j = 0; str1[i]; ++i, ++j) {



            Given that we're iterating over strings, it's more idiomatic to use a char pointer than to repeatedly index into the string (though a good compiler ought to generate the same code):



            static bool helper_one_way(const char *a, const char *b,
            bool allow_deletion)

            size_t nchars = 0;
            while (*a)
            if (*a++ != *b++)
            if (++nchars > 1) return false;
            if (allow_deletion) --b;


            return true;




            Finally: the name - should one_way be spelt one_away?




            Modified code



            Applying the above suggestions, we get:



            #include <stdbool.h>
            #include <string.h>

            static bool helper_one_away(const char *a, const char *b,
            bool allow_deletion)

            size_t nchars = 0;
            while (*a)
            if (*a++ != *b++)
            if (++nchars > 1) return false;
            if (allow_deletion) --b;


            return true;


            /* Return true if a can be obtained from string2 by adding,
            deleting, or removing at most one character */
            bool one_away(const char *a, const char *b)

            switch (strlen(a) - strlen(b))
            case (size_t)-1: return helper_one_away(b, a, true);
            case 0: return helper_one_away(a, b, false);
            case 1: return helper_one_away(a, b, true);
            default: return false;




            /* Test code */

            #include <stdio.h>

            /* return number of test failures (0 or 1) */
            static int test_one_away(const char *a, const char *b,
            bool expected)

            const int actual = one_away(a, b);
            if (actual == expected)
            return 0;
            fprintf(stderr, "one_away "%s", "%s" expected %d but got %dn",
            a, b, expected, actual);
            return 1;


            int main(void)

            return
            + test_one_away("", "", true)
            + test_one_away("", "a", true)
            + test_one_away("pale", "", false)
            + test_one_away("pale", "le", false)
            + test_one_away("pale", "ale", true)
            + test_one_away("pale", "pale", true)
            + test_one_away("pale", "pal", true)
            + test_one_away("pale", "pa", false)
            + test_one_away("pale", "ple", true)
            + test_one_away("ple", "pale", true)
            + test_one_away("pales", "pale", true)
            + test_one_away("pale", "bale", true)
            + test_one_away("pale", "bake", false);







            share|improve this answer












            share|improve this answer



            share|improve this answer










            answered 6 hours ago









            Toby SpeightToby Speight

            30.6k7 gold badges45 silver badges132 bronze badges




            30.6k7 gold badges45 silver badges132 bronze badges











            • $begingroup$
              bool makes its debut in C99 after including <stdbool.h>. OP cannot use it.
              $endgroup$
              – Deduplicator
              3 hours ago
















            • $begingroup$
              bool makes its debut in C99 after including <stdbool.h>. OP cannot use it.
              $endgroup$
              – Deduplicator
              3 hours ago















            $begingroup$
            bool makes its debut in C99 after including <stdbool.h>. OP cannot use it.
            $endgroup$
            – Deduplicator
            3 hours ago




            $begingroup$
            bool makes its debut in C99 after including <stdbool.h>. OP cannot use it.
            $endgroup$
            – Deduplicator
            3 hours ago











            0












            $begingroup$

            1. Using a size_t for a boolean flag, and calling it flag, is nearly an obfuscation. Use int pre-C99 and call it something descriptive like substitute.


            2. strlen() is likely a waste, though it makes describing the algorithm easier. Try to do without the additional iteration.


            3. Getting the length of the longest common prefix looks like a well-defined task which can be extracted, and a useful building-block. Do so.


            4. one_way, one_away, or one_microsoft_way? Having a properly-spelled correctly-selected name is Always very important.



            5. Change to a single-traversal algorithm:



              Remove he common prefix.



              Measuring the common prefix without the first characters is quite instructive.



              With x and y different from a, call n = strlen_common(++a, ++b):




              1. At most one substitution at the start:



                xaaaabcde
                yaaaabcde


                Result n == 8, a[n] == b[n].




              2. Deletion from the first:



                xaaaabcde
                aaaabcde


                n == 3, strcmp(a + n, b + n - 1) != 0



              3. Same way for deletion from second.



            The modified code (also live on coliru):



            size_t strlen_common(const char* a, const char* b) 
            size_t r = 0;
            while (*a && *a++ == *b++)
            ++r;
            return r;


            int one_away(const char* a, const char* b) !b[1];
            if (!*b)
            return !a[1];
            n = strlen_common(++a, ++b);
            return a[n] == b[n]






            share|improve this answer











            $endgroup$

















              0












              $begingroup$

              1. Using a size_t for a boolean flag, and calling it flag, is nearly an obfuscation. Use int pre-C99 and call it something descriptive like substitute.


              2. strlen() is likely a waste, though it makes describing the algorithm easier. Try to do without the additional iteration.


              3. Getting the length of the longest common prefix looks like a well-defined task which can be extracted, and a useful building-block. Do so.


              4. one_way, one_away, or one_microsoft_way? Having a properly-spelled correctly-selected name is Always very important.



              5. Change to a single-traversal algorithm:



                Remove he common prefix.



                Measuring the common prefix without the first characters is quite instructive.



                With x and y different from a, call n = strlen_common(++a, ++b):




                1. At most one substitution at the start:



                  xaaaabcde
                  yaaaabcde


                  Result n == 8, a[n] == b[n].




                2. Deletion from the first:



                  xaaaabcde
                  aaaabcde


                  n == 3, strcmp(a + n, b + n - 1) != 0



                3. Same way for deletion from second.



              The modified code (also live on coliru):



              size_t strlen_common(const char* a, const char* b) 
              size_t r = 0;
              while (*a && *a++ == *b++)
              ++r;
              return r;


              int one_away(const char* a, const char* b) !b[1];
              if (!*b)
              return !a[1];
              n = strlen_common(++a, ++b);
              return a[n] == b[n]






              share|improve this answer











              $endgroup$















                0












                0








                0





                $begingroup$

                1. Using a size_t for a boolean flag, and calling it flag, is nearly an obfuscation. Use int pre-C99 and call it something descriptive like substitute.


                2. strlen() is likely a waste, though it makes describing the algorithm easier. Try to do without the additional iteration.


                3. Getting the length of the longest common prefix looks like a well-defined task which can be extracted, and a useful building-block. Do so.


                4. one_way, one_away, or one_microsoft_way? Having a properly-spelled correctly-selected name is Always very important.



                5. Change to a single-traversal algorithm:



                  Remove he common prefix.



                  Measuring the common prefix without the first characters is quite instructive.



                  With x and y different from a, call n = strlen_common(++a, ++b):




                  1. At most one substitution at the start:



                    xaaaabcde
                    yaaaabcde


                    Result n == 8, a[n] == b[n].




                  2. Deletion from the first:



                    xaaaabcde
                    aaaabcde


                    n == 3, strcmp(a + n, b + n - 1) != 0



                  3. Same way for deletion from second.



                The modified code (also live on coliru):



                size_t strlen_common(const char* a, const char* b) 
                size_t r = 0;
                while (*a && *a++ == *b++)
                ++r;
                return r;


                int one_away(const char* a, const char* b) !b[1];
                if (!*b)
                return !a[1];
                n = strlen_common(++a, ++b);
                return a[n] == b[n]






                share|improve this answer











                $endgroup$



                1. Using a size_t for a boolean flag, and calling it flag, is nearly an obfuscation. Use int pre-C99 and call it something descriptive like substitute.


                2. strlen() is likely a waste, though it makes describing the algorithm easier. Try to do without the additional iteration.


                3. Getting the length of the longest common prefix looks like a well-defined task which can be extracted, and a useful building-block. Do so.


                4. one_way, one_away, or one_microsoft_way? Having a properly-spelled correctly-selected name is Always very important.



                5. Change to a single-traversal algorithm:



                  Remove he common prefix.



                  Measuring the common prefix without the first characters is quite instructive.



                  With x and y different from a, call n = strlen_common(++a, ++b):




                  1. At most one substitution at the start:



                    xaaaabcde
                    yaaaabcde


                    Result n == 8, a[n] == b[n].




                  2. Deletion from the first:



                    xaaaabcde
                    aaaabcde


                    n == 3, strcmp(a + n, b + n - 1) != 0



                  3. Same way for deletion from second.



                The modified code (also live on coliru):



                size_t strlen_common(const char* a, const char* b) 
                size_t r = 0;
                while (*a && *a++ == *b++)
                ++r;
                return r;


                int one_away(const char* a, const char* b) !b[1];
                if (!*b)
                return !a[1];
                n = strlen_common(++a, ++b);
                return a[n] == b[n]







                share|improve this answer














                share|improve this answer



                share|improve this answer








                edited 4 mins ago

























                answered 3 hours ago









                DeduplicatorDeduplicator

                13k20 silver badges55 bronze badges




                13k20 silver badges55 bronze badges



























                    draft saved

                    draft discarded
















































                    Thanks for contributing an answer to Code Review Stack Exchange!


                    • Please be sure to answer the question. Provide details and share your research!

                    But avoid


                    • Asking for help, clarification, or responding to other answers.

                    • Making statements based on opinion; back them up with references or personal experience.

                    Use MathJax to format equations. MathJax reference.


                    To learn more, see our tips on writing great answers.




                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function ()
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f223872%2fcracking-the-coding-interview-1-5-one-away%23new-answer', 'question_page');

                    );

                    Post as a guest















                    Required, but never shown





















































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown

































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown







                    Popular posts from this blog

                    Canceling a color specificationRandomly assigning color to Graphics3D objects?Default color for Filling in Mathematica 9Coloring specific elements of sets with a prime modified order in an array plotHow to pick a color differing significantly from the colors already in a given color list?Detection of the text colorColor numbers based on their valueCan color schemes for use with ColorData include opacity specification?My dynamic color schemes

                    Invision Community Contents History See also References External links Navigation menuProprietaryinvisioncommunity.comIPS Community ForumsIPS Community Forumsthis blog entry"License Changes, IP.Board 3.4, and the Future""Interview -- Matt Mecham of Ibforums""CEO Invision Power Board, Matt Mecham Is a Liar, Thief!"IPB License Explanation 1.3, 1.3.1, 2.0, and 2.1ArchivedSecurity Fixes, Updates And Enhancements For IPB 1.3.1Archived"New Demo Accounts - Invision Power Services"the original"New Default Skin"the original"Invision Power Board 3.0.0 and Applications Released"the original"Archived copy"the original"Perpetual licenses being done away with""Release Notes - Invision Power Services""Introducing: IPS Community Suite 4!"Invision Community Release Notes

                    199年 目錄 大件事 到箇年出世嗰人 到箇年死嗰人 節慶、風俗習慣 導覽選單